Leetcode 309. Best Time to Buy and Sell Stock with Cooldown

这道题用的是dp的思想，用buy, sell, cooldown记录当前这些状态下最多的profit。

对于day i 而言：

      sell[i] = buy[i-1] + prices[i]

      buy[i] = max(muy[i-1], cooldown[i-1] - prices[i])

      cooldown[i] = max(cooldown[i-1], sell[i-1])

空间优化：由于每次只需要知道上一次的情况，因此可以不使用数组，直接用变量记录sell, buy, cooldown

 

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
            
        #buy, sell, cooldown表示三种状态下最多的资金
        #用第一天进行初始化
        buy, sell, cooldown = -prices[0], 0, 0
        
        for i in range(1, len(prices)):
            last_sell = sell
            sell = buy + prices[i]
            buy = max(buy, cooldown - prices[i])
            cooldown = max(cooldown, last_sell)
        
        return max(sell, cooldown)