動機

可以當成188的暖身題

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

  • After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: prices = [1,2,3,0,2]Output: 3Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1]Output: 0

 

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

Sol

把buy與sell分開，要算出在買與賣之間的最大收益

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

但這是看前一天的，現在賣完要慢一天才能買，所以改成

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

class Solution:
    @functools.cache
    def buy(self,i):
        if i < 0:
            return 0
        elif i == 0:
            return -self.prices[i]
        else:
            return max(self.sell(i-2)-self.prices[i], self.buy(i-1))
    @functools.cache
    def sell(self,i):
        if i <= 0:
            return 0
        else:
            return max(self.buy(i-1)+self.prices[i],self.sell(i-1))
    def maxProfit(self, prices: List[int]) -> int:
        # buy[i] = sell[i-1] - prices[i] | buy[i-1]
        # sell[i] = buy[i-1] + prices[i] | sell[i-1]
        # buy must be delayed, which has cooldown before sell
        # take sell[i-2] when do buy
        self.prices = prices
        return self.sell(len(prices)-1)