参考文献
ref{:target=”_blank”}
状态机,动态规划
状态规划 f(i, j) 表示第i天处于第j(0,1,3)状态的最大收益
C++ 代码
class Solution {
public:
// 状态规划 f(i, j) 表示第i天处于第j(0,1,3)状态的最大收益
// f(i, 0) 表示 冷却期、未持有股票状态
// f(i, 1) 表示 持有股票状态
// f(i, 2) 表示 恰好交易的状态(即从状态1过来,随即进入状态0)
// 状态 0 可以直接向1转移,因为2先到1,然后到0,中间至少一天的冷冻期了
int maxProfit(vector<int>& prices) {
int n = prices.size();
// 使用2维数组优化存储空间
vector<vector<int>> f(2, vector<int>(3, -1e8));
f[0][0] = 0, f[0][1] = -prices[0];
for(int i=1; i<n; ++i){
f[i&1][0] = max(f[i-1&1][0], f[i-1&1][2]);
f[i&1][1] = max(f[i-1&1][1], f[i-1&1][0]-prices[i]);
f[i&1][2] = f[i-1&1][1]+prices[i];
}
int res = max(f[n-1&1][0], max(f[n-1&1][1], f[n-1&1][2]));
return res;
}
};