Say you have an array for which the ith element is the PRice of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
現(xiàn)在給你一個數(shù)組，第i個元素代表第i天的股票價格。設計出一個算法去找到最大的收益。允許多次交易，但是你必須在第二次買股票前賣掉股票，而且當你賣掉股票，第二天你不被允許買股票（冷卻時間）
prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]
動態(tài)規(guī)劃解。思考問題仍然從如何找到第i天和前一天的最大收益的關系出發(fā)。我們可以發(fā)現(xiàn)每一天都有三種狀態(tài)，即買（buy），賣（sell），不買不賣（rest），那么其實我們可以分別記錄第i天buy, sell, rest的最大收益記錄下來，然后根據(jù)它們之間的關系更新。這個思路完全沒有問題，但是在實際操作的時候我們會發(fā)現(xiàn)，rest其實也要分兩種情況。
第一種是sell后，buy前的rest，因為sell后不能馬上buy，所以如果第i天是rest_before_buy，那么第i - 1天只能是rest_before_buy本身或者sell第二種是buy后，sell前的rest，如果第i天是rest_after_buy，那么第i - 1天只能是rest_after_buy或者buy所以這兩種rest并不是同一種，因此其實每一天有四種狀態(tài)，即rest_before_buy, buy, rest_after_buysell, sell，關系如下圖
關系式為：
buy[i] = rest_before_buy[i - 1] - prices[i]
rest_after_buy[i] = max(buy[i - 1], rest_after_buy[i - 1])
sell[i] = max(buy[i - 1] + prices[i], rest_after_buy[i - 1] + prices[i])
rest_before_buy[i] = max(sell[i - 1], rest_before_buy[i - 1])
初始化為：
buy[0] = -prices[0] # 第一天買進花費prices[0]
rest_after_buy[0] = -prices[0] # 因為是不買不賣，所以和buy[0]相同
sell[0] = - (prices[0] + 1) # 第一天不可能賣的，所以設一個非常小的值
rest_before_buy = 0 # 第一天如果不買不賣，花費0
代碼
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) == 0: return 0 sell = [0] * len(prices) buy = [0] * len(prices) rest_before_buy = [0] * len(prices) rest_after_buy = [0] * len(prices) # 初始化 buy[0] = - prices[0] sell[0] = - (prices[0] + 1) rest_after_buy[0] = - prices[0] for index_p in range(1, len(prices)): buy[index_p] = rest_before_buy[index_p - 1] - prices[index_p] rest_after_buy[index_p] = max(buy[index_p - 1], rest_after_buy[index_p - 1]) sell[index_p] = max(rest_after_buy[index_p - 1] + prices[index_p], buy[index_p - 1] + prices[index_p]) rest_before_buy[index_p] = max(sell[index_p - 1], rest_before_buy[index_p - 1]) # 因為最后一天buy或者rest_after_buy（有股票沒賣掉）都不可能利益最大的，所以不需比較 return max(sell[-1], rest_before_buy[-1])新聞熱點
疑難解答
