原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown

解法1:

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
    状态机模型
    与传统股票问题一样 总体上来看也是持股、不持股两个状态
    由于存在冷冻期 
    将不持股这个状态再拆分为 不进行操作的不持股状态 和 卖了股票后因冷冻期而不能操作的不持股状态

    f[i][j] 表示前i天 持股状态为j时  可获得的最大现金
    f[i][0] 没有操作而不持股票 
    f[i][1] 持股
    f[i][2] 卖出股票后处于冷静期而不能持股
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] f = new int [n][3];

        // 初始值
        // 初始无操作 现金为0 
        f[0][0] = 0;
        // 初始持股 
        f[0][1] = -prices[0];
        /// 初始卖出股票处于冷静期
        f[0][2] = 0;

        for(int i = 1 ;i < n ; i++){
            // 不操作状态可以由 本身就不操作 或者 冷静期转移而来
            f[i][0] = Math.max(f[i - 1][0],f[i - 1][2]); 
            // 不操作 或者 买入
            f[i][1] = Math.max(f[i - 1][1],f[i - 1][0] - prices[i]);
            // 只能由 f[i][1] 转移而来
            f[i][2] = Math.max(f[i - 1][2],f[i - 1][1] + prices[i]);
        }

        // 不持股 现金才是最大的
        return  Math.max(f[n - 1][0],f[n - 1][2]);
    }
}