[059] LeetCode 123演算法【Best Time to Buy and Sell Stock III】股票機器人 III

Published in

Leetcode 演算法教學

6 min readOct 17, 2020

123. Best Time to Buy and Sell Stock III (Hard)

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 at most two transactions.

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

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

這題有兩個簡單的小規定

只能交易兩次。
每一次只可以交易一筆。

在解這種有很多種選項的題目，建議是用DP Table去解，做一個動態規劃，在使用動態規劃做題之前，要先去看題目符不符合下面三點：

最佳子結構性質。如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。最佳子結構性質為動態規劃演算法解決問題提供了重要線索。
無後效性。即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。
子問題重疊性質。子問題重疊性質是指在用遞迴演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地檢視一下結果，從而獲得較高的效率，降低了時間複雜度。

如果有從頭跟著刷題的朋友應該可以看得出來，動態規劃其實就是遞迴的延伸，以這一題為例子的話我們可以直接用他的狀態來設計DP表格，每一天分別都會有三個狀態：買入、賣出、不操作，我們可以定義出buy、sell、doNothing，這三個狀態又有分一些定義:

sell要在buy之後，賣完才能買，買完才能賣
交易次數k，只能在k大於0的情況下交易
兩種doNothing，sell之後，buy之後(不能多次交易)

上面做的事情叫做枚舉(窮舉)，我們先把所有的可能性都舉出來，這樣好建造表格。
他將會是一個三維的array:
dp[i][k][0 or 1]
i=天數
k=交易次數
0 or 1 = 能否交易(1=不能(持有股票),0=可以(不持有股票))
用上面的資訊來推斷我們可以很清楚的知道
0<= i <=n-1 , 1<=k<=T
n為天數，T為最多交易數
所以這題的所有狀態將會是 n x K x 2 種狀態如果用以上的公式來定義的話，我們可以得很清楚的解釋下面的資料
dp[1][2][1] : 今天第一天，至今最多進行2次交易，目前持有股票所以無法交易
dp[3][1][0] : 今天第三天，至今最多進行1次交易，目前手上沒有股票可以交易

狀態轉移

窮舉出所有可能性以後，接下來要做的是狀態轉移，也就是要思考每一種狀態有哪一些選擇，定義這些選擇可以幫助我們達到我們要的結果，我們可以先看能否交易的0跟1，0要到1一定要執行buy這個動作，1到0要執行sell這個動作，當你在0或1上面doNothing的時候本身還是會在0跟1上。

所以我們可以很清楚的只要去比對前一天有買股票跟沒有買股票的利潤就好了，也就是

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(選擇doNothing  , 選擇sell)
今天沒股票：昨天就沒有今天休息，昨天有股票我今天賣了dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
              max(選擇doNothing  , 選擇buy)
今天有股票：昨天就有股票，今天休息，昨天沒股票今天買

理解了這一步，就只剩下初始化最原始的base case了，畢竟要先定義一個狀態，才可以從此狀態出發到下一個狀態，可以回想我們寫斐波那契数列的時候有初始化過會比較好理解:

if (n <= 0) return 0;
if (n == 1) return 1;

看到這邊有些同學可能覺得有點暈了，有了上面這些觀念，我們可以介紹一種很簡單的思考路線，就是把函式的解，存在Array裡面，有了這個概念以後，我們可以簡單的定義出每天有四種狀態。

1.昨天買過股票，今天賣掉的最大值
2.昨天買過股票，今天不賣的最小值
3.昨天沒買股票，今天買股票的最大值
4.昨天買過股票，今天不賣的最小值

大家加油。

上一篇：[058] LeetCode 122演算法【Best Time to Buy and Sell Stock II】股票機器人 II

下一篇：[060] LeetCode 188演算法【Best Time to Buy and Sell Stock IV】股票機器人 IV

[059] LeetCode 123演算法【Best Time to Buy and Sell Stock III】 股票機器人 III

Written by M

[059] LeetCode 123演算法【Best Time to Buy and Sell Stock III】股票機器人 III