309. 最佳买卖股票时机含冷冻期（高频题）

309. 最佳买卖股票时机含冷冻期

• 解题思路
• 代码

解题思路

买卖股票问题都可以用动态规划，具体思路见这里

---

写状态转移方程的时候注意，绝大部分都是找到前一个状态和目前状态的关系
比如：

dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);

即：有两种情况

1. 第i-1天就没有股票，且第i-1天也没有进行卖出
2. 第i-1天有股票，但是它在第i-1天就卖出了

---

dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);

即：有两种情况

1. 第i-1天就拥有的股票一直保存到第i天，第i-1天需要拥有股票，没有进行卖出行为
2. 第i天购买的股票，第i天需要购买股票则要求第i-1天非冷却期，即第i-1天没有进行卖出行为，也就是代号0满足这个条件；

---

dp[i][2]=dp[i-1][1]+prices[i];

即：今天由于卖出不持股，那肯定是由于前一天持股，今天卖出了转移而来。

代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0||prices.length==1){
            return 0;
        }
        // dp[i][j] 表示 [0, i] 区间内，在下标为 i 这一天状态为 j 时，我们手上拥有的收益
        int[][] dp=new int[prices.length][3];

 // dp[i][0]: 手上不持有股票，并且今天不是由于卖出股票而不持股，我们拥有的收益
        dp[0][0]=0;
// dp[i][1]: 手上持有股票时，我们拥有的收益
        dp[0][1]=-prices[0];//持股。初始收益就是第一天股价的负数。
// dp[i][2]: 手上不持有股票，并且是由于卖出股票而不持股，我们拥有的收益
        dp[0][2]=0;

        for(int i=1;i<prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=dp[i-1][1]+prices[i];
        }
//最后要在不持股的状态中选一个最大的，因为最后一天还持有股票肯定是对收益的损害！
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
    }
}