309. 最佳买卖股票时机含冷冻期

题目分析

这个题目的题眼在于状态转换的比较多.

我认为最好的一种解法是使用了三个一维DP数组维护状态.

1. buy_dp
2. sell_dp
3. cool_dp

使用了三个一维DP数组的好处

1. 空间换复杂度, 更多的空间, 可以使我们的状态转化更容易的表达.

buy_dp的状态

1. buy_dp[i]的状态可以从cool_dp[i-1]和buy_dp[i-1]来转化过来.
2. buy_dp[i]和buy_dp[i-1]的空状态.

代码自解释.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        
        if n == 0:
            return 0
        # 状态解释
        # buy_dp[i] 表示的是在 i 进行买入操作的最大收益
        # sell_dp[i] 表示的是在 i 进行卖出操作的最大收益
        # cool_dp[i] 表示的是在 i 处于冷冻期的时候的最大收益
        buy_dp = [0]*n
        sell_dp = [0]*n
        cool_dp = [0]*n
        
        # 状态初始化
        
        buy_dp[0] = -prices[0]
        sell_dp[0] = 0
        cool_dp[0] = 0
        
        for i in range(1,n):
            # buy_dp[i] = buy_dp[i-1]表示的是空操作
            # buy_dp[i] = cool_dp[i-1]-prices[i-1] 
            # 表示的是从冷却期状态 转化出来, 开始买入
            buy_dp[i] = max(buy_dp[i-1],cool_dp[i-1]-prices[i])
            # sell_dp[i] = sell_dp[i-1] 表示的是空操作
            # sell_dp[i] = buy_dp[i-1]+prices[i]
            # 表示状态转换, 从买入状态进入卖出状态
            sell_dp[i] = max(sell_dp[i-1], buy_dp[i-1]+prices[i])
            
            # cool_dp[i] = cool_dp[i-1] 表示空操作
            # cool_dp[i] = sell_dp[i-1] 表示的是状态转换
            cool_dp[i] = max(cool_dp[i-1], sell_dp[i-1])
        # 最后的状态是卖出或者cooldown 的最大值
        return max(sell_dp[-1],cool_dp[-1])