多状态动态规划之最佳买卖股票时机含冷冻期

雨点打透心脏的1/2处 2024-03-17 13:00 60阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [最佳买卖股票时机含冷冻期][Link 1]  
![image.png][]  
结合示例 1 来看 :  
![image.png][image.png 1]  
也就是说, 对于操作而言始终是买入, 卖出, 冻结三次一循环. 分别循环对应到我们的prices 数组. 并且每次我们只能操作手里的一支股票, 只有这只股票卖出并且不在冻结期内才可以购买下一支股票. 最终求取获得的最大利润.

在来看示例 2  
![image.png][image.png 2]  
根据我们之前说的交易状态循环, 它不是买入嘛 ? 最终获利 - 1 猜对 ? 其实不然, 这里讲解的是特殊情况, 也就是针对于当天我们可以不进行操作.

什么意思呢 ? 也就是说, 如果当天股票太贵, 我不想买入了也可以.**手上一支股票也没有这时候是自由状态, 买入以后就处于可卖出状态, 卖出以后就处于冻结状态, 冻结过后就又处于自由状态, 可以选择是否买入.**

**同样的, 如果我当前是买入状态, 我可以选择不卖出, 结束后同样还是处于买入状态**

## 2. 转态表示 ##

以 i 为结尾, 从第一天开始到第 i 天结束时所获得的最大利润.

到达第 i 天时, 又有三种不同的交易状态, 因此对于这个状态表示我们还可以接着细分.

**因为交易状态是三次一循环的. 数组的长度为 n, n % 3 结果为 0 则认为是买入状态, 结果为 1 则认为是可交易状态, 结果为 2 则认为是冻结状态**

**可交易状态 : 当前你已经卖出去了, 手里没有股票, 并且不出在冻结期**

1.  第 i 天结束时处于买入状态

这种情况我们表示为 dp\[i\]\[0\], 即第 i 天结束时, 处于买入状态所获得的最大利润

1.  第 i 天结束时处于可交易状态

这种情况我们表示为 dp\[i\]\[1\], 即第 i 天结束时, 处于可交易状态所获得的最大利润

1.  第 i 天结束时处于冻结状态

这种情况我们表示为 dp\[i\]\[2\], 即第 i 天结束时, 处于冻结状态所获得的最大利润

**它是一个多状态的动态规划问题. 有多个状态表示, 同时也会有多个状态转移方程.**

## 3. 状态转移方程 ##

针对上面的三个不同状态, 我们分别来分析一下对应的状态转移方程. 想要知道第 i 天的情况, 那么就需要分析 i - 1 天的情况

1.  第 i 天结束时处于买入状态

如何才能在第 i 天结束时处于买入状态呢 ?

1.1 第 i - 1 天时处于买入状态, 第 i 天时不操作, 第 i 天结束后依然为买入状态

则当前利润对应到状态表示中为 i - 1 天结束处于可买入状态, 即 dp\[i-1\]\[0\]

1.2. 第 i - 1 天时处于可交易状态, 第 i 天时买入, 第 i 天结束后则处于买入状态

则当前利润对应到状态表示中为 i - 1 天结束处于可交易状态, 即 dp\[i-1\]\[1\], 并且第i 天花钱买入股票, 最终第 i 天结束此时利润为 dp\[i-1\]\[1\] - prices\[i\]

**最终 dp\[i\]\[0\] = Math.max( dp\[i-1\]\[1\] - prices\[i\], dp\[i-1\]\[0\] ) 这两种情况的最大收益**

1.  第 i 天结束时处于可交易状态
    
    2.2 第 i - 1 天处于可交易状态, 第 i 天不操作, 则第 i 天接受后依然为可交易状态
    
    则当前利润对应到状态表示中为第 i - 1 天结束处于可交易状态, 即 dp\[i-1\]\[1\]
    
    2.1 第 i - 1 天处于冷冻期, 第 i 天不操作, 那么第 i 天结束后则处于可交易状态
    
    则当前利润对应到状态表示中为第 i - 1 天结束处于冻结期, 即 dp\[i-1\]\[2\]

**最终 dp\[i\]\[1\] = Math.max(dp\[i-1\]\[1\], dp\[i-1\]\[2\] )**

1.  第 i 天结束时处于冻结状态
    
    3.1 第 i - 1 天处于买入状态, 第 i 天卖出, 则第 i 天结束后处于冷冻状态

则当前利润对应到状态表示中为第 i - 1 天结束处于买入状态, 即 dp\[i-1\]\[0\], 并且第 i 天卖出股票, 利润为 dp\[i-1\]\[0\] + prices\[i\]

**最终 dp\[i\]\[2\] = dp\[i-1\]\[0\] + prices\[i\]**

## 4. 初始化 ##

根据状态转移方程, 可以看到填表时 dp\[0\]\[0\] 和 dp\[0\]\[1\] 以及 dp\[0\]\[2\] 会发生越界错误, 因此这三个位置需要初始化.

1.  第 0 结束后处于买入状态, 意味着当天必须买入这只股票, 因此当前最大利润为 -prices\[0\] ( **负值 !** )
2.  第 0 天结束后处于交易状态, 要想处于交易状态, 说明这天我们什么都没做, 为自由状态. 最大利润为 0
3.  **第 0 天结束后处于冻结期, 意味着第 0 天当天不可能是冻结期, 等同于第 0 天买了又买了, 最后获利为 0**

## 5. 填表顺序 ##

根据状态转移方程, 填表顺序为从左往右, 一次需要填写 3 列. 即每天的三种状态对应的不同状态的最大利润

## 6. 返回值 ##

返回值则是第 n 天结束后, 三种状态下对应利润的最大值.  
**需要考虑的是, 第一种情况买入状态下, 可以不需要考虑. 比如你手上有一支股票, 没有卖出去处于买入状态, 哪势必比你手上没有股票时利润小. 不管你是因为卖出去了没有股票还是冷冻期没有股票, 都是卖出去了手上的股票, 因此一定比你没卖出去当前手上股票获利多.**

**最终, 我们只需要考虑第 n 天结束时, 处于交易状态和冷冻期时的最大利润即可.**  
**即 Math.max( dp\[n-1\]\[1\], dp\[n-1\]\[2\] )**

## 7. 代码演示 ##

public int maxProfit(int[] prices) {
        
    
            // 1. 创建 dp 表
            int n = prices.length;
            int[][] dp = new int[n][3];
    
            // 2. 初始化
            dp[0][0] = -prices[0];
    
            // 3. 填写 dp 表
            for(int i = 1; i < n; i++) {
        
                // 根据状态转移方程填写
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
                dp[i][2] = dp[i - 1][0] + prices[i];
            }
        
            // 4. 确认返回值
            return Math.max(dp[n - 1][1], dp[n - 1][2]);
        }

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/afcbb3b27fe64245a0c5eeb560bcb12b.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/05df4cbd82a9403b93f9d5c8ca4e97be.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/09fd27373c344c4a81a87397283e15fe.png