LeetCode0309.BestTimetoBuyandSellStockwithCooldown[Medium][Python][动态编程]有一个数组，其中第i个元素是价格第i天的给定股票。设计一个算法来找到最大利润。您可以根据需要完成任意数量的交易（即多次买入和卖出一股股票），但有以下限制：您不得同时进行多项交易（即，您必须先卖出股票，然后再进行交易）再买）。卖出股票后，第二天就不能再买入股票。（即冷却时间1天）示例：输入：[1,2,3,0,2]输出：3解释：transactions=[buy,sell,cooldown,buy,sell]给定的问题是一个整数数组，其中第i个元素表示第i天的股票价格。设计一个算法来计算最大利润。您可以完成尽可能多的交易（多次买入和卖出一只股票），但须遵守以下限制：您不能同时参与多笔交易（您必须先卖出之前的股票，然后才能再次买入）。卖出股票后，次日不能买入该股票（即冻结期为1天）。例子：输入：[1,2,3,0,2]输出：3解释：对应的交易状态为：[买入，卖出，冻结期，买入，卖出]动态规划思想求状态方程dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])解释：昨天没有股票,但有昨天股票今天卖出dp[i][k][1]=max(dp[i-1][k][1],dp[i-2][k][0]-prices[i])解释：昨天还有存货，前天刚卖出。昨天冻结期间，今天第i天买入，选择买入时，需要从i-2状态转出，而不是i-1状态。基本情况：dp[-1][k][0]=dp[i][k][0]=0dp[-1][k][1]=dp[i][k][1]=-infk=+inf因为k是正无穷大，那么k和k-1可以看成是一样的。buy+sell=一次完整的交易，这里把sell看成一次交易，所以第一行是k-1。dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k-1][1]+价格[i])=max(dp[i-1][k][0],dp[i-1][k][1]+价格[i])dp[i][k][1]=max(dp[i-1][k][1],dp[i-2][k][0]-prices[i])因此k对状态转换没有影响：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+价格[i])dp[i][1]=max(dp[i-1][1],dp[i-2][0]-价格[i])i=0,dp[i-1]无效。dp[0][0]=max(dp[-1][0],dp[-1][1]+prices[i])=max(0,-infinity+prices[i])=0dp[0][1]=max(dp[-1][1],dp[-1][0]-prices[i])=max(-infinity,0-prices[i])=-prices[i]空间复杂度：O(1)Python3代码类解决方案：defmaxProfit(self,prices:List[int])->int:dp_i_0=0dp_i_1=float('-inf')#负无穷dp_pre_0=0#表示dp[i-2][0]foriinrange(len(prices)):temp=dp_i_0#昨天没有库存，但昨天有库存，今天卖出dp_i_0=max(dp_i_0,dp_i_1+prices[i])#dp_i_0而dp_i_1可以当成一个变量，存储的值是最后一次的值，也就是昨天。#我昨天有股票，前天刚卖掉股票。我今天在冻结期间买了它们。dp_i_1=max(dp_i_1,dp_pre_0-prices[i])dp_pre_0=tempreturndp_i_0codeAddressGitHublinkreferenceOnemethodkill6库存问题
