[LeetCode] 309、最佳买卖股票时机含冷冻期

题目描述给定一个整数数组其中第i个元素代表了第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。输入:[1,2,3,0,2]输出:3解释:对应的交易状态为:[买入,卖出,冷冻期,买入,卖出]解题思路“股票买卖”这个系列有好几道题labuladong大佬有一个“一个通用方法团灭 6 道股票问题”推荐相似问题解题方法统一一下不然容易做每个题都用不同的方法总结不出套路。动态规划三把斧动态规划因为本题中规定买入卖出和冷冻操作规定上一次卖出和下一次买入之间需要至少一天的冷冻期因此我们定义三种状态sell、buy和cooldown分别对应了到第i天为止最后一个操作是买入、卖出和冷冻所对应的最大利润注意并不是第i天就是那个操作例如第i-1天卖出第i天无操作则第i天为止最后一个操作也是卖出操作sell[i]则状态转移方程如下此题对状态表示的理解很重要sell[i] max(sell[i-1], buy[i-1] prices[i]);buy[i] max(buy[i-1], cooldown[i-1] - prices[i]);cooldown[i] max(cooldown[i-1], sell[i-1]);注如何理解第i-1天是sell状态第i天还是sell呢?其实是这样的sell[i]代表的是到第i天为止最后一个操作是卖出操作即昨天卖出今天无操作或者昨天买入今天卖出两种状态所以sell[i] max(sell[i-1], buy[i-1] prices[i]);。即我们可以把第i天分为确实有操作第i天进行了买入/卖出/冷冻操作和无操作两种状态。参考代码辣鸡代码不要看这玩意classSolution{public:intmaxProfit(vectorintprices){intlengthprices.size();if(length0)return0;intbuy[length],sell[length],cooldown[length];memset(buy,0,sizeof(buy));// 用vectorint buy(length,0) 更方便memset(sell,0,sizeof(sell));memset(cooldown,0,sizeof(cooldown));buy[0]-prices[0];// 初始化第一天只能执行买入操作for(inti1;ilength;i){buy[i]max(buy[i-1],cooldown[i-1]-prices[i]);sell[i]max(sell[i-1],buy[i-1]prices[i]);cooldown[i]max(cooldown[i-1],sell[i-1]);}returnsell[length-1];// 最后一定是返回这个}};一个通用方法团灭 6 道股票问题// 每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题122、买卖股票的最佳时机 II 的状态转移方程即可// dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])// dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])// 解释第 i 天选择 buy 的时候要从第 i-2 天的状态转移而不是 i-1 。classSolution{public:intmaxProfit(vectorintprices){intlengthprices.size();if(length1){return0;}intdp_i_00,dp_i_1-prices[0];intdp_pre_00;// 可以理解为“前天没有股票”这种状态for(inti1;ilength;i){inttempdp_i_0;dp_i_0max(dp_i_0,dp_i_1prices[i]);dp_i_1max(dp_i_1,dp_pre_0-prices[i]);dp_pre_0temp;}returndp_i_0;}};