團滅 LeetCode 股票買賣問題
- 2019 年 10 月 11 日
- 筆記
預計閱讀時間： 12分鐘
上篇文章 LeetCode 股票問題的一種通用解法 用遞歸的方法實現了一套簡單易懂的可行解，但是時間複雜度略高，不能通過全部測試用例。
這篇文章用「狀態機」的技巧給出最優解，可以全部提交通過。不要覺得這個名詞高大上，文學詞彙而已，實際上就是 DP table，等會兒一講就明白了。
先隨便抽一道題出來，看看別人發的解法：
能看懂吧？會做了吧？不可能的，你看不懂，這才正常。就算你勉強看懂了，下一個問題你還是做不出來。那為什麼別人能寫出這麼詭異卻又高效的解法呢？因為這類問題是有框架的，但是人家不會告訴你的，因為一旦告訴你，你十分鐘就學會了，該算法題就不再神秘，變得不堪一擊了。
本文就來告訴你處理這類問題的框架，拒絕奇技淫巧，穩紮穩打，以不變應萬變。
這 6 道題目是有共性的，本文通過對第四道題的分析，逐步解決所有問題。因為第四題是一個最泛化的形式，其他的問題都是這個形式的簡化。看下題目：
第一題是只進行一次交易，相當於 k = 1；第二題是不限交易次數，相當於 k = +infinity（正無窮）；第三題是只進行 2 次交易，相當於 k = 2；剩下兩道也是不限交易次數，但是加了交易「冷凍期」和「手續費」的額外條件，其實就是第二題的變種，都很容易處理。
如果你還不熟悉題目，可以去 LeetCode 或者上篇文章 一種通用思路 查看這些題目的內容，本文為了節省篇幅，就不列舉這些題目的具體內容了。下面言歸正傳，開始詳解。
一、窮舉框架
首先，還是一樣的思路：如何窮舉？這裡的窮舉思路和上篇文章遞歸的思想不太一樣。
遞歸其實是符合我們思考的邏輯的，一步步推進，遇到無法解決的就丟給遞歸，一不小心就做出來了，可讀性還很好。缺點就是一旦出錯，你也不容易找到錯誤出現的原因。比如上篇文章的遞歸解法，肯定還有計算冗餘，但確實不容易找到。
而這裡，我們不用遞歸思想進行窮舉，而是利用「狀態」進行窮舉。
看看總共有幾種「狀態」，再找出每個「狀態」對應的「選擇」。我們要窮舉所有「狀態」，窮舉的目的是根據對應的「選擇」更新狀態。看圖，就是這個意思。
具體到當前問題，每天都有三種「選擇」：買入、賣出、無操作，我們用 buy, sell, rest 表示這三種選擇。
但問題是，並不是每天都可以任意選擇這三種選擇的，因為 sell 必須在 buy 之後，buy 必須在 sell 之後（第一次除外）。那麼 rest 操作還應該分兩種狀態，一種是 buy 之後的 rest（持有了股票），一種是 sell 之後的 rest（沒有持有股票）。而且別忘了，我們還有交易次數 k 的限制，就是說你 buy 還只能在 k > 0 的前提下操作。
很複雜對吧，不要怕，我們現在的目的只是窮舉，你有再多的狀態，老夫要做的就是一把梭全部列舉出來。這個問題的「狀態」有三個，第一個是天數，第二個是當天允許交易的最大次數，第三個是當前的持有狀態（即之前說的 rest 的狀態，我們不妨用 1 表示持有，0 表示沒有持有）。
我們用一個三維數組 dp 就可以裝下這幾種狀態的全部組合，用 for 循環就能完成窮舉：
而且我們可以用自然語言描述出每一個狀態的含義，比如說 dp[3][2][1] 的含義就是：今天是第三天，我現在手上持有着股票，至今最多進行 2 次交易。再比如 dp[2][3][0] 的含義：今天是第二天，我現在手上沒有持有股票，至今最多進行 3 次交易。很容易理解，對吧？
我們想求的最終答案是 dp[n – 1][K][0]，即最後一天，最多允許 K 次交易，所能獲取的最大利潤。讀者可能問為什麼不是 dp[n – 1][K][1]？因為 [1] 代表手上還持有股票，[0] 表示手上的股票已經賣出去了，很顯然後者得到的利潤一定大於前者。
記住如何解釋「狀態」，一旦你覺得哪裡不好理解，把它翻譯成自然語言就容易理解了。
二、狀態轉移框架
現在，我們完成了「狀態」的窮舉，我們開始思考每種「狀態」有哪些「選擇」，應該如何更新「狀態」。
因為我們的選擇是 buy, sell, rest，而這些選擇是和「持有狀態」相關的，所以只看「持有狀態」，可以畫個狀態轉移圖。
通過這個圖可以很清楚地看到，每種狀態（0 和 1）是如何轉移而來的。根據這個圖，我們來寫一下狀態轉移方程：
這個解釋應該很清楚了，如果 buy，就要從利潤中減去 prices[i]，如果 sell，就要給利潤增加 prices[i]。今天的最大利潤就是這兩種可能選擇中較大的那個。而且注意 k 的限制，我們在選擇 buy 的時候，把最大交易數 k 減小了 1，很好理解吧，當然你也可以在 sell 的時候減 1，一樣的。
現在，我們已經完成了動態規劃中最困難的一步：狀態轉移方程。如果之前的內容你都可以理解，那麼你已經可以秒殺所有問題了，只要套這個框架就行了。不過還差最後一點點，就是定義 base case，即最簡單的情況。
把上面的狀態轉移方程總結一下：
讀者可能會問，這個數組索引是 -1 怎麼編程表示出來呢，負無窮怎麼表示呢？這都是細節問題，有很多方法實現。現在整體框架已經完成，下面開始具體化。
三、秒殺題目
第一題，k = 1
直接套狀態轉移方程，根據 base case，可以做一些化簡：
直接翻譯成代碼：
顯然 i = 0 時 dp[i-1] 是不合法的。這是因為我們沒有對 i 的 base case 進行處理。那就簡單粗暴地處理一下：
第一題就解決了，但是這樣處理 base case 很麻煩，而且注意一下狀態轉移方程，新狀態只和相鄰的一個狀態有關，其實不用整個 dp 數組，只需要兩個變量儲存所需的狀態就足夠了，這樣可以把空間複雜度降到 O(1):
兩種方式都是一樣的，不過這種編程方法簡潔很多。但是如果沒有前面狀態轉移方程的引導，是肯定看不懂的。後續的題目，我主要寫這種空間複雜度 O(1) 的解法。
第二題，k = +infinity
如果 k 為正無窮，那麼就可以認為 k 和 k – 1 是一樣的。可以這樣改寫框架：
直接翻譯成代碼即可：
第三題，k = +infinity with cooldown
每次 sell 之後要等一天才能繼續交易。只要把這個特點融入上一題的狀態轉移方程即可：
直接翻譯成代碼即可：
第四題，k = +infinity with fee
每次交易要支付手續費，只要把手續費從利潤中減去即可：
直接翻譯成代碼即可：
第五題，k = 2
k = 2 和前面題目的情況稍微不同，因為上面的情況都和 k 的關係不太大。要麼 k 是正無窮，狀態轉移和 k 沒關係了；要麼 k = 1，跟 k = 0 這個 base case 挨得近，最後也被消掉了。
這道題 k = 2 和後面要講的 k 是任意正整數的情況中，對 k 的處理就凸顯出來了。我們直接寫代碼，邊寫邊分析原因。
按照之前的代碼，我們可能想當然這樣寫代碼（錯誤的）：
為什麼錯誤？我這不是照着狀態轉移方程寫的嗎？
還記得前面總結的「窮舉框架」嗎？就在強調必須窮舉所有狀態。其實我們之前的解法，都在窮舉所有狀態，只是之前的題目中 k 都被化簡掉了，所以沒有對 k 的窮舉。比如說第一題，k = 1：
這道題由於沒有消掉 k 的影響，所以必須要用 for 循環對 k 進行窮舉才是正確的：
如果你不理解，可以返回第一點「窮舉框架」重新閱讀體會一下。
第二種解法：因為這裡 k 取值範圍比較小，所以也可以不用 for 循環，直接把 k = 1 和 2 的情況手動列舉出來也是一樣的：
有狀態轉移方程和含義明確的變量名引導，相信你很容易看懂。如我我們想故弄玄虛，可以把上述四個變量換成 a, b, c, d。這樣當別人看到你的解法時就會大驚失色，一頭霧水，不得不對你肅然起敬。
第六題，k = any integer
這題和 k = 2 沒啥區別，可以直接套上一題的第一個解法。但是提交之後會出現一個超內存的錯誤，原來是傳入的 k 值可以任意大，導致 dp 數組太大了。現在想想，交易次數 k 最多能有多大呢？
一次交易由買入和賣出構成，至少需要兩天。所以說有效的限制次數 k 應該不超過 n/2，如果超過，就沒有約束作用了，相當於 k = +infinity。這種情況是之前解決過的。
直接把之前的代碼重用：
至此，6 道題目通過一個狀態轉移方程全部解決。
四、最後總結
本文給大家講了如何通過狀態轉移的方法解決複雜的問題，用一個狀態轉移方程秒殺了 6 道股票買賣問題，現在想想，其實也不算難對吧？而這已經屬於動態規劃問題中較困難的了。
關鍵就在於找到所有可能的「狀態」，然後想想怎麼更新這些「狀態」。一般用一個多維 dp 數組儲存這些狀態，從 base case 開始向後推進，推進到最後的狀態，就是我們想要的答案。想想這個過程，你是不是有點理解「動態規劃」這個名詞的意義了呢？
具體到股票買賣問題，我們發現了三個狀態，使用了一個三維數組，無非還是窮舉 + 更新，不過我們可以說的高大上一點，這叫「三維 DP」，怕不怕？這個大實話一說，立刻顯得你高人一等有沒有？
