关于动态规划【力扣309.买卖股票的最佳时机含冷冻期的思考】

1、与前四题股票系列的关系【力扣121.买卖股票的最佳时机I】只能买卖1次【力扣122.买卖股票的最佳时机II】可以买卖多次【力扣123.买卖股票的最佳时机III】只能买卖2次【力扣188.买卖股票的最佳时机IV】至多买卖k次本题【309.买卖股票的最佳时机含冷冻期】是在【力扣122.买卖股票的最佳时机II】基础上多加了一个冷冻期。即可以买卖多次冷冻期。2、关键思路【dp数组的状态表示有四种】根据前面几题的经历我们一般会思考到三种情况持有股票、不持有股票、冷冻期。那么本题最主要的一个思路就是把第二种不持有股票的情况进一步细分。为什么要进行这个行为呢是为了让dp数组表示的状态更全面。因为这道题比较特殊多了一个冷冻期。什么时候会出现冷冻期就是在前一天有具体“卖出”股票行为的时候会出现这个特殊情况。所以需要在不持有股票的情况里单独细分一个卖出股票的状态这样就可以推出冷冻期的状态然后其他天数不持有股票的行为被重命名为“保持卖出”状态。3、递推关系dp[i][0]表示持有股票的最大利润。这个最大利润有可能来自“前一天就是持有股票”的状态、”前一天是冷冻期今天买入了股票“的状态、“前一天是保持卖出股票今天买入了股票”的状态。在这三种状态里取最大值就是当前持有股票的最大利润。dp[i][1]表示保持卖出的最大利润。这个最大利润有可能来自“前一天就是保持卖出”的状态、”前一天是冷冻期“的状态。在这两种状态里取最大值就是当前保持卖出股票的最大利润。dp[i][2]表示卖出股票的最大利润。这个最大利润只可能来自“前一天就是持有股票”的状态因为只有持有股票才能卖出股票。dp[i][3]表示冷冻期的最大利润。这个最大利润只可能来自“前一天就是卖出股票”的状态因为只有卖出股票第二天才会进入冷冻期。4、dp数组初始化问题根据递推关系可以判断要初始化的dp数组元素是第0天的各种状态dp[0][0] -prices[0]; // dp[0][0]表示第0天持有股票的状态。可以抽象理解为第0天一开始什么也不做的最大利润是0元第0天经历了买入股票那么现在手头上的最大利润是0-prices[0]元dp[0][1] 0; // dp[0][1]表示第0天保持卖出的状态。可以抽象理解为第0天经历了买入、卖出、冷冻期那么现在手头上的最大利润还是0元dp[0][2] 0; // dp[0][2]表示第0天卖出股票的状态。可以抽象理解为第0天经历了买入、卖出那么现在手头上的最大利润还是0元dp[0][3] 0; // dp[0][3]表示第0天冷冻期的状态。可以抽象理解为第0天经历了买入、卖出现在经历冷冻期那么现在手头上的最大利润还是0元5、特别注意C语法max()函数里最多传入两个参数修复一下如下图所示