[Leetcode][第309题][JAVA][最佳买卖股票时机含冷冻期][动态规划][压缩空间]

女爷i 2023-02-25 02:18 2阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 动态规划 ######

动态规划流程  
**第 1 步：设计状态**  
f\[i\]表示第 i 天结束之后的「累计最大收益」  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**第 2 步：状态转移方程**

f\[i\]\[0\]=max(f\[i−1\]\[0\],f\[i−1\]\[2\]−prices\[i\])  
f\[i\]\[1\]=f\[i−1\]\[0\]+prices\[i\]  
f\[i\]\[2\]=max(f\[i−1\]\[1\],f\[i−1\]\[2\])

**第 3 步：考虑初始化**  
![在这里插入图片描述][2020071010371391.png]  
**第 4 步：考虑输出**  
max(f\[n−1\]\[0\],f\[n−1\]\[1\],f\[n−1\]\[2\]) ➡ max(f\[n−1\]\[1\],f\[n−1\]\[2\])

**第 5 步：考虑是否可以状态压缩**  
可 见方法2

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

**f\[0\]\[1\] 置为0**

> 因为f\[1\]\[1\]只和f\[0\]\[0\]有关系，f\[0\]\[1\]只影响f\[1\]\[2\],而f\[1\]\[2\]又是由f\[0\]\[1\]和f\[0\]\[2\]共同决定的，第0天f\[0\]\[1\]和f\[0\]\[2\]是同一状态也就无所谓了。

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200710103838663.png]

class Solution { 
        public int maxProfit(int[] prices) { 
            if (prices.length == 0) { 
                return 0;
            }
    
            int n = prices.length;
            // f[i][0]: 手上持有股票的最大收益
            // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
            // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
            int[][] f = new int[n][3];
            f[0][0] = -prices[0];
            for (int i = 1; i < n; ++i) { 
                f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
                f[i][1] = f[i - 1][0] + prices[i];
                f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
            }
            return Math.max(f[n - 1][1], f[n - 1][2]);
        }
    }

###### 2. 动态规划路径压缩 ######

![在这里插入图片描述][20200710103337137.png]  
**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int maxProfit(int[] prices) { 
            if (prices.length == 0) { 
                return 0;
            }
    
            int n = prices.length;
            int f0 = -prices[0];
            int f1 = 0;
            int f2 = 0;
            for (int i = 1; i < n; ++i) { 
                int newf0 = Math.max(f0, f2 - prices[i]);
                int newf1 = f0 + prices[i];
                int newf2 = Math.max(f1, f2);
                f0 = newf0;
                f1 = newf1;
                f2 = newf2;
            }
    
            return Math.max(f1, f2);
        }
    }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2. 三个状态 三数组DP 两数组DP信息量过大 处理不来 ######

转载链接：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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/787e9735551c4cd08c73b5382d0d05e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/04cd2f0afcbe4cd5bdb83f8f4af48504.png
[2020071010371391.png]: https://img-blog.csdnimg.cn/2020071010371391.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200710103540368.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200710103838663.png]: https://img-blog.csdnimg.cn/20200710103838663.png
[20200710103337137.png]: https://img-blog.csdnimg.cn/20200710103337137.png