題目分析

這個題目的題眼在于狀態(tài)轉(zhuǎn)換的比較多.

我認為最好的一種解法是使用了三個一維DP數(shù)組維護狀態(tài).

1. buy_dp
2. sell_dp
3. cool_dp

使用了三個一維DP數(shù)組的好處

1. 空間換復(fù)雜度, 更多的空間, 可以使我們的狀態(tài)轉(zhuǎn)化更容易的表達.

buy_dp的狀態(tài)

1. buy_dp[i]的狀態(tài)可以從cool_dp[i-1]和buy_dp[i-1]來轉(zhuǎn)化過來.
2. buy_dp[i]和buy_dp[i-1]的空狀態(tài).

代碼自解釋.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        
        if n == 0:
            return 0
        # 狀態(tài)解釋
        # buy_dp[i] 表示的是在 i 進行買入操作的最大收益
        # sell_dp[i] 表示的是在 i 進行賣出操作的最大收益
        # cool_dp[i] 表示的是在 i 處于冷凍期的時候的最大收益
        buy_dp = [0]*n
        sell_dp = [0]*n
        cool_dp = [0]*n
        
        # 狀態(tài)初始化
        
        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] 
            # 表示的是從冷卻期狀態(tài) 轉(zhuǎn)化出來, 開始買入
            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]
            # 表示狀態(tài)轉(zhuǎn)換, 從買入狀態(tài)進入賣出狀態(tà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] 表示的是狀態(tài)轉(zhuǎn)換
            cool_dp[i] = max(cool_dp[i-1], sell_dp[i-1])
        # 最后的狀態(tài)是賣出或者cooldown 的最大值
        return max(sell_dp[-1],cool_dp[-1])