状态机

$ 时间复杂度O(NK),空间复杂度O(2NK))$

状态转移方程发现，状态只和上一层相关，所以我们可以压缩一维空间，使得空间复杂度O(2K)

初始化也只需要初始化f[0][0] = 0,即交易0次，手中无股票的最大值，其余负无穷

参考文献

算法提高课

AC代码

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