309.买卖股票的最佳时机包括冻结期买卖股票带冷却时间题目给定一个整数数组，第i个元素代表第i天的股票价格。设计一个算法来计算最大利润。您可以完成尽可能多的交易（多次买入和卖出一只股票），但须遵守以下限制：您不能同时参与多笔交易（您必须先卖出之前的股票，然后才能再次买入）。卖出股票后，次日不能买入该股票（即冻结期为1天）。示例：输入：[1,2,3,0,2]输出：3解释：对应的交易状态为：[买入，卖出，冻结期，买入，卖出]解题思路：动态规划先复习题，标题说不能同时参与多笔交易，需要先卖出之前买入的股票再买入。同时，会有一段冻结期。题目中给出的解释是，某日股票卖出后，第二天不能再买入，即卖出后的第二天为休息日。因为买卖有这个冻结期，所以我们先分清楚是不是持有股票，然后再把这个概念加入讨论。首先定义两个dp数组，分别代表持股和不持股的累计最大收益。状态定义首先定义状态，定义两个数组own和not_own。其中，own[i]表示第i天持有股票的最大收益；not_own[i]表示第i天不持股的最大收益。状态转换现在讨论冻结期的概念。上面两个数组在进行状态转换时会有不同的情况，如下：对于own[i]，表示第i天持有股票的最大收益。可能出现的情况拆分如下：第i-1天持有，第i天继续持有；第i-1天为冻结期，则第i天买入（即前天卖出，当天买入价为prices[i]）；那么此时的状态转移方程为：own[i]=max(own[i-1],not_own[i-2]-prices[i])对于not_own[i]，也可以拆分为如下情况：第i-1天卖出，第i天属于冻结期；第i-1天持有股票，第i天卖出股票；那么此时的状态转移方程为：not_own[i]=max(not_own[i-1],own[i-1]+prices[i])这里，两个数组之间发生了状态转移。先说own[i]的状态转移方程。第一种情况很好理解，第二种情况可以这样理解，因为类似交易的收益是这样计算的：收益=卖出-买入。然后直接扣掉当天需要买的钱（就是先减去进货价），然后在后面卖的时候，这部分就不计算了，直接加上卖价。这种情况也和not_own[i]的第二种情况一致，直接把当前股价加上前i-1天的收益（因为之前已经扣除了）。初始化own[0]：表示第0天购买，前面分析过，这里直接减去购买价格，所??以own[0]=-prices[0];own[1]：表示可以在第0天买入，第一天继续持有；或者在第一天购买，所以own[1]=max(-prices[0],-prices[1])。not_own[0]：表示第0天没有持有股票，所以没有盈利，not_own[0]=0具体代码实现如下。代码实现类解决方案：defmaxProfit(self,prices:List[int])->int:ifnotpricesorlen(prices)==1:return0length=len(prices)own=[0]*lengthnot_own=[0]*length#初始化own[0]=-prices[0]own[1]=max(-prices[0],-prices[1])not_own[0]=0foriinrange(1,length):not_own[i]=max(not_own[i-1],own[i-1]+prices[i])如果i==1:继续own[i]=max(own[i-1],not_own[i-2]-prices[i])returnmax(own[-1],not_own[-1])实际结果欢迎关注公众号【书所集录】
