leetcode 309 股票买卖 冷冻期

状态主要分为两种，一种是天数，一种是是否持股以及是否处在冷冻期，这两种状态是复合的，要么持有，要么不持有不冷冻，要么不持有在冷冻。
所以设置dp数组，状态转移如下
dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i])
dp[i][2]=max(dp[i-1][1],dp[i-1][2])
dp[i][1]=dp[i-1][0]+prices[i]
其中处在冷冻期只有一种情况就是昨天持有，今天卖掉

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0 for _ in range(3)] for _ in range(len(prices))]
        dp[0][0]=-prices[0]
        dp[0][1]=float('-inf')
        dp[0][2]=0

        for i in range(1,len(prices)):
            dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i])
            dp[i][2]=max(dp[i-1][1],dp[i-1][2])
            dp[i][1]=dp[i-1][0]+prices[i]

        return max(dp[len(prices)-1][2],dp[len(prices)-1][1])

空间优化

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        onhand=-prices[0]
        nohand_cold=float('-inf')
        nohand_nocold=0

        for i in range(1,len(prices)):
           f0=max(onhand,nohand_nocold-prices[i])
           f1=onhand+prices[i]
           f2=max(nohand_cold,nohand_nocold)
           onhand=f0
           nohand_cold=f1
           nohand_nocold=f2


        return max(nohand_nocold,nohand_cold)