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

Example

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

Solution

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

所以這兩種rest并不是同一種，因此其實(shí)每一天有四種狀態(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)花費(fèi)prices[0]

rest_after_buy[0] = -prices[0] # 因?yàn)槭遣毁I不賣，所以和buy[0]相同

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

rest_before_buy = 0 # 第一天如果不買不賣，花費(fèi)0

代碼