188. 买卖股票的最佳时机 IV

和123. 买卖股票的最佳时机 III一样的DP解法。

注意对(0)的特判。

class Solution {
public:
    int f[1010][2][110];
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n == 0) return 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<=k;j++)
            {
                if(i == 0)
                {
                    f[i][0][j]=0;
                    f[i][1][j]=-prices[i];
                }
                else
                {
                    f[i][0][j]=f[i-1][0][j];
                    if(j) f[i][0][j]=max(f[i][0][j],f[i-1][1][j-1]+prices[i]);
                    f[i][1][j]=max(f[i-1][1][j],f[i-1][0][j]-prices[i]);
                }
            }
        return f[n-1][0][k];
    }
};