Question

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天的股票價格。設(shè)計出一個算法去找到最大的收益。允許多次交易，但是你必須在第二次買股票前賣掉股票，而且當(dāng)你賣掉股票，第二天你不被允許買股票（冷卻時間）

Example

prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

Solution

動態(tài)規(guī)劃解。思考問題仍然從如何找到第i天和前一天的最大收益的關(guān)系出發(fā)。我們可以發(fā)現(xiàn)每一天都有三種狀態(tài)，即買（buy），賣（sell），不買不賣（rest），那么其實我們可以分別記錄第i天buy, sell, rest的最大收益記錄下來，然后根據(jù)它們之間的關(guān)系更新。這個思路完全沒有問題，但是在實際操作的時候我們會發(fā)現(xiàn)，rest其實也要分兩種情況。

所以這兩種rest并不是同一種，因此其實每一天有四種狀態(tài)，即rest_before_buy, buy, rest_after_buysell, sell，關(guān)系如下圖

關(guān)系式為：

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] # 第一天買進(jìn)花費prices[0]

rest_after_buy[0] = -prices[0] # 因為是不買不賣，所以和buy[0]相同

sell[0] = - (prices[0] + 1) # 第一天不可能賣的，所以設(shè)一個非常小的值

rest_before_buy = 0 # 第一天如果不買不賣，花費0

代碼