朴素dp
f[i][j]:第j天前最多交易i次的最大收益

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

记录一个最大值，优化一维时间

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

滚动数组优化空间

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