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