面向大象程式設計
「股票買賣問題」大概是每個刷 LeetCode 的同學都會遇到的一大攔路虎，特别是其中的第三道題。你是否也曾因為這道題而懵逼呢？
股票買賣系列問題
LeetCode 上的股票買賣系列問題一共六道，形成一個巨大的系列，蔚為壯觀。系列的前兩道題并不難，可以通過思維轉換得到解法。然而就在你以為整個系列都可以循序漸進地做出來時，第三道題的難度陡然上升，讓人猝不及防。
更令人沮喪的是，這樣一道難題，打開讨論區，看到的卻是一份異常裝逼的題解代碼：
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int s1 = Integer.MIN_VALUE, s2 = 0,
s3 = Integer.MIN_VALUE, s4 = 0;
for (int p : prices) {
s1 = Math.max(s1, -p);
s2 = Math.max(s2, s1 + p);
s3 = Math.max(s3, s2 - p);
s4 = Math.max(s4, s3 + p);
}
return Math.max(0, s4);
} WTF?? 這謎一樣的四個變量
s1
/
s2
/
s3
/
s4
是怎麼回事？這種計算方式怎麼能展現題目中「最多買賣兩次」的限制？
不要慌張。其實這類問題是有套路的，隻要掌握了套路，你也一樣能寫出這樣裝逼的解法。這個套路也非常實用，幾道股票買賣問題都可以用這個套路解出來。
這樣實用而裝逼的解法，今天就讓我為你細細講述。本文會介紹股票買賣問題的這個解法中涉及到的幾個技巧：
- 動态規劃子問題的狀态拆解與狀态機定義
- DP 數組的特殊值定義
- 動态規劃的空間優化技巧
問題解法
我們來求解最典型的股票問題（三），它是其他幾道題目解法的基礎：
LeetCode 123. Best Time to Buy and Sell Stock III（Hard）
給定一個數組，它的第
個元素是一支給定的股票在第
天的價格。設計一個算法來計算你所能擷取的最大利潤。你最多可以完成兩筆交易。
注意： 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例：
輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3。
随後，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3。
很多同學可能已經隐約想到這道題是用動态規劃來解，但是一直想不出來合适的具體思路。
這道題最大的難點就在于其限制條件「最多完成兩筆交易」。如何在動态規劃中描述這個限制條件？如何記錄股票買賣過程中的「不同狀态」？其實，全部的答案就在我們上一篇文章中讨論的技巧：拆分動态規劃的子問題。
不記得上一篇文章内容的同學可以點這裡回顧：
LeetCode 例題精講 | 17 動态規劃如何拆分子問題，簡化思路
當然，如果你隻想知道股票買賣問題的解法，可以直接往下看。
狀态機定義
對于題目中「最多完成兩筆交易」這個限制條件，我們可以了解成：股票買賣的過程，經曆了不同的階段。
- 在一開始，限制是「最多完成兩筆交易」；
- 做完一筆交易之後，限制變成「隻做一筆交易」；
- 做完兩筆交易之後，限制變成「不能再做交易」。
有的解法選擇定義一個參數
來表示可以進行交易的數量。不過
另外，題目中還有一個條件是「再次購買前必須賣掉之前的股票」，這實際上又給股票買賣過程劃分了階段。我們有「持有股票」和「不持有股票」兩種狀态。在持有股票的時候，隻能賣出，不能買入。不持有股票的時候則反之。
總體來看，做兩筆交易，則股票買賣的過程可以分為五個階段：
| 階段 | 可交易次數 | 持股狀态 | 可買入/賣出 |
| 2 | 不持有 | 可買入 | |
| 1 | 1 | 持有 | 可賣出 |
| 2 | 1 | 不持有 | 可買入 |
| 3 | 持有 | 可賣出 | |
| 4 | 不持有 | 可買入 |
股票買賣過程的五個階段
對應這五個階段，我們可以定義五個子問題，分别用
、
、
、
、
來表示。字母 s 代表狀态，股票買賣階段的變化，其實就是狀态的轉移。
例如在階段 1，我們持有股票，此時如果賣出股票，則變成不持有股票的狀态，進入階段 2。
~
子問題間的狀态轉移關系（狀态機）
在每一天，我們既可以選擇買入/賣出，又可以選擇不進行買賣。選擇買入或者賣出的話，就會進入下一個階段，對應狀态轉移圖中向右的邊；選擇不買賣的話，會繼續待在目前階段，對應狀态轉移圖中的環路。
這就是所謂的「狀态機 DP」。定義多個子問題，從另一個角度來看，就是子問題在不同的「狀态」間跳來跳去。
在了解了子問題之間的關系之後，我們正式地定義一下子問題和遞推關系：子問題
分别表示「前
- 。因為階段 0 時沒有任何買入賣出。
-
。第 k 天處于階段 1，可能是前一天處于階段 1，或者是前一天處于階段 0，然後買入了第 k 天的股票（利潤減去
）。
-
。第 k 天處于階段 2，可能是前一天處于階段 2，或者是前一天處于階段 1，然後賣出了第 k 天的股票（利潤增加
）。
-
。分析同
。
-
。分析同
。
了解 DP 數組
在定義了子問題及其遞推關系後，我們還需要搞清楚 DP 數組的計算順序。
首先，由于
始終為 0，我們其實不需要計算，直接作為常數 0 代入即可。這樣就隻剩
/
/
/
四個子問題中，
的取值範圍都是
。這樣我們的 DP 數組是四個長度為
DP 數組
接着是 DP 數組中的依賴關系：
DP 數組的依賴關系
可以看出，DP 數組的計算順序是從左到右、從上到下。我們可以根據這個寫出初步的題解代碼：
// 注意：這段代碼并不完整
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int[] s1 = new int[n+1];
int[] s2 = new int[n+1];
int[] s3 = new int[n+1];
int[] s4 = new int[n+1];
// 注意：這裡還缺少 base case 的指派
for (int k = 1; k <= n; k++) {
s1[k] = Math.max(s1[k-1], -p[k-1]);
s2[k] = Math.max(s2[k-1], s1[k-1] + p[k-1]);
s3[k] = Math.max(s3[k-1], s2[k-1] - p[k-1]);
s4[k] = Math.max(s4[k-1], s3[k-1] + p[k-1]);
}
return Math.max(0, Math.max(s2[n], s4[n]));
} 處理 base case
上面的代碼還不是很完整，我們還需要填上子問題的 base case 的取值。
對于這道題來說，确定 base case 的取值并不容易。難點在于 DP 數組中的部分元素是無效的。
以
為例，
的含義應該是：在第 0 天（即一開始），經過一次買入、一次賣出後，所獲的最大利潤。然而我們在第 0 天顯然還不能進行任何買賣，那麼
就是無效元素。我們可以推出，
在
同樣的道理，我們可以計算出
、
、
、
的 base case 分别是
、
、
、
，如下圖所示（這裡放上
DP 數組中的無效元素
如果用條件判斷來處理這些無效元素，代碼會變得非常複雜。有沒有什麼更好的方法呢？
答案是給
、
、
、
既然最終結果要求的是最大利潤（max），我們可以給這些無效元素賦一個比任何可能結果都小的值：
-
對于
、
，這個值是
。因為這兩個狀态不持有股票，有效值顯然不會低于 0（可以不買也不賣，利潤就是 0）。
-
對于
、
，這個值是
。因為這兩個狀态要持有股票，買入後會出現暫時的負利潤。
加入這些 base case 之後，我們得到完整的代碼：
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int[] s1 = new int[n+1];
int[] s2 = new int[n+1];
int[] s3 = new int[n+1];
int[] s4 = new int[n+1];
s1[0] = Integer.MIN_VALUE;
s2[0] = 0;
s3[0] = Integer.MIN_VALUE;
s4[0] = 0;
for (int k = 1; k <= n; k++) {
s1[k] = Math.max(s1[k-1], -prices[k-1]);
s2[k] = Math.max(s2[k-1], s1[k-1] + prices[k-1]);
s3[k] = Math.max(s3[k-1], s2[k-1] - prices[k-1]);
s4[k] = Math.max(s4[k-1], s3[k-1] + prices[k-1]);
}
return Math.max(0, Math.max(s2[n], s4[n]));
} 空間優化
上面的代碼已經比較簡潔了，不過它和我們一開始展示的裝逼型代碼還有一點差距。接下來，我們使用一點空間優化的技巧，讓代碼更加簡潔。
回顧一下上面的 DP 數組依賴圖：
DP 數組的依賴關系
我們發現，每一列的值都隻依賴于上一列的值。這樣，我們隻需要儲存目前一列的值，然後在每一輪疊代中計算下一列的值。
空間優化方案，疊代計算每一列
這樣，
s1
、
s2
、
s3
、
s4
就從一維數組變成了單個變量。
int s1 = Integer.MIN_VALUE;
int s2 = 0;
int s3 = Integer.MIN_VALUE;
int s4 = 0;
for (int k = 1; k <= n; k++) {
s4 = Math.max(s4, s3 + prices[k-1]);
s3 = Math.max(s3, s2 - prices[k-1]);
s2 = Math.max(s2, s1 + prices[k-1]);
s1 = Math.max(s1, -prices[k-1]);
} 上面的代碼中大量出現
prices[k-1]
。我們把
k-1
替換成
k
：
int s1 = Integer.MIN_VALUE;
int s2 = 0;
int s3 = Integer.MIN_VALUE;
int s4 = 0;
for (int k = 0; k < n; k++) {
s4 = Math.max(s4, s3 + prices[k]);
s3 = Math.max(s3, s2 - prices[k]);
s2 = Math.max(s2, s1 + prices[k]);
s1 = Math.max(s1, -prices[k]);
} 然後把 for 循環改成 for-each 循環：
int s1 = Integer.MIN_VALUE;
int s2 = 0;
int s3 = Integer.MIN_VALUE;
int s4 = 0;
for (int p : prices) {
s4 = Math.max(s4, s3 + p);
s3 = Math.max(s3, s2 - p);
s2 = Math.max(s2, s1 + p);
s1 = Math.max(s1, -p);
} 這樣，我們就得到了最終的簡化版代碼：
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int s1 = Integer.MIN_VALUE;
int s2 = 0;
int s3 = Integer.MIN_VALUE;
int s4 = 0;
for (int p : prices) {
s4 = Math.max(s4, s3 + p);
s3 = Math.max(s3, s2 - p);
s2 = Math.max(s2, s1 + p);
s1 = Math.max(s1, -p);
}
return Math.max(0, Math.max(s2, s4));
} 這樣一步步看下來，是不是感覺開頭那個裝逼的代碼也沒有那麼難懂了？
總結
本文一步步剖析了股票買賣問題的解題技巧。如果你直接看最終的代碼，會覺得「裝逼」而放棄這道題。但跟着本文的思路一步步走，會發現這樣的代碼其實是經過一步步的簡化，逐漸變成這個樣子的。
LeetCode 讨論區的很多答案喜歡炫耀代碼的簡潔，比拼行數。但是追求代碼的極簡并不利于我們掌握問題思路。對于本題而言，其實最值得掌握的是沒有經過空間優化的、定義四個一維數組的代碼。特别是在面試中，如果你一上來就寫出了經過空間優化後的極簡代碼，面試官可能覺得你是在「背題」，反而對你印象不好。
本文講述的股票問題的解法有人稱之為「狀态機 DP」。解法的關鍵就在于定義多個子問題，然後描述子問題之間的狀态轉移關系。讀完本文的同學，強烈建議把股票買賣問題跟上一篇文章中的例題聯系起來看，會讓你對這一類問題有更深的了解。
股票買賣系列的其他問題同樣可以用這個解題技巧做出來。後面的文章我會給大家展示如何把「最多完成兩筆交易」擴充到「最多完成 k 筆交易」的通用版題目，以及帶有交易手續費和冷卻期的變種題目的求解方法，敬請期待。
由 五分鐘學算法 原班人馬打造的公衆号：圖解面試算法，現已正式上線！
接下來我們将會在該公衆号上，為大家分享優質的算法解題思路，堅持每天一篇原創文章的輸出，感興趣的小夥伴可以關注一下哈！