题解 | #牛群买卖计划# 状态机DP

知识点

状态机DP

思路

定义 f[i][j][st] 前i天完成j笔交易，手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态，就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    const int INF = 0x3f3f3f3f;
    int f[100010][4][2]; // f[i][j][st] 前i天完成j笔交易 手上股票持有状态为st 的最大值
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        for (int i = 0; i <= 3; i ++) {
            f[0][i][0] = f[0][i][1] = -INF;
        }
        f[0][0][0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= 3; j ++) {
                // 不动 / 进行买卖
                f[i][j][0] = max(f[i - 1][j][1] + prices[i - 1], f[i - 1][j][0]);
                f[i][j][1] = max(f[i - 1][j - 1][0] - prices[i - 1], f[i - 1][j][1]);
            }
        }
        int res = 0;
        for (int i = 0; i <= 3; i ++) {
            res = max(res, f[n][i][0]);
        }
        return res;
    }
};