leetcode 309. Best Time to Buy and Sell Stock with Cooldown | 309. 最佳买卖股票时机含冷冻期（动态规划）

冷不防 2022-10-13 12:57 164阅读 0赞

## 题目 ##

[https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/][https_leetcode.com_problems_best-time-to-buy-and-sell-stock-with-cooldown]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

我知道要dp，但是不知道要怎么dp，最后还是看了答案。。

参考：[官方题解][Link 1]

##### 力扣平台上的股票类型的题目 #####

这是一个系列

121.买卖股票的最佳时机  
122.买卖股票的最佳时机 II  
123.买卖股票的最佳时机 III  
188.买卖股票的最佳时机 IV  
309. 最佳买卖股票时机含冷冻期（本题）  
714.买卖股票的最佳时机含手续费  
剑指 Offer 63. 股票的最大利润

一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

##### 动态规划解法 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

##### 代码 #####

class Solution { 
        public int maxProfit(int[] prices) { 
            int[][] dp = new int[prices.length][3];
            dp[0][0] = -prices[0];
            for (int i = 1; i < prices.length; i++) { 
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
                dp[i][1] = dp[i - 1][0] + prices[i];
                dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            }
            return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
        }
    }

[https_leetcode.com_problems_best-time-to-buy-and-sell-stock-with-cooldown]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/cb99e5b0e8f54479bd96211450709632.png
[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/68d0a79de9e948a38bbdd24d03736b22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/459fe411d2234d7cac2e358328028785.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/b4b08600c86a4dc0ad7ea3d4f7d7082b.png