用狀態(tài)機(jī)的技巧（不要害怕敷燎，其實(shí)就是DP table）來解決股票買賣問題，可以全部提交通過兰绣。

leetcode 買賣股票的最佳時(shí)機(jī)的 6 道題是有共性的搪柑，看下 IV 題吮蛹，是最泛化的形式，其他的問題都是這個(gè)形式的簡化：

第 I 題是只進(jìn)行一次交易拌屏， 相當(dāng)于 k = 1;

第 II 題是不限交易次數(shù)潮针，相當(dāng)于 k = +INF；

第 III 題是只進(jìn)行2次交易倚喂，相當(dāng)于 k = 2每篷；

剩下兩道題也是不限次數(shù)瓣戚，但是加了交易?「冷凍期」和「?續(xù)費(fèi)」的額外條件，其實(shí)就是第二題的變種焦读，都很容易處理子库。

一、窮舉框架

如何窮舉矗晃？窮舉和遞歸的思想不太一樣仑嗅。遞歸其實(shí)是符合我們思考的邏輯的：一步步推進(jìn)，遇到無法解決的就丟給遞歸张症，一不小心就做出來仓技，可讀性還很好。缺點(diǎn)就是一旦出錯(cuò)俗他，也不容易找到錯(cuò)誤出現(xiàn)的原因脖捻。

這里我們利用「狀態(tài)」進(jìn)?窮舉。具體到每一天兆衅，看看總共有幾種可能的「狀態(tài)」地沮，再找出每個(gè)「狀態(tài)」對(duì)應(yīng)的選擇，窮舉的目的是根據(jù)對(duì)應(yīng)的「選擇」更新狀態(tài)羡亩。

比如這個(gè)問題摩疑，每天都有三種「選擇」：買入（buy）、賣出(sell)畏铆、無操作(rest)雷袋。但這三種選擇不是相互獨(dú)立的：sell 必須在 buy 之后。并且操作還應(yīng)該分兩種狀態(tài)及志，一種是未持有（0）的操作，一種是已持有（1）后的操作寨腔。并且速侈，剩余可交易次數(shù) k 還限制 buy 只能在 k>0 的前提下操作。

這個(gè)問題的「狀態(tài)」有三個(gè)： 第?個(gè)是天數(shù)迫卢；第?個(gè)是允許交易的最?次數(shù)倚搬；第三個(gè)是當(dāng)前的持有狀態(tài)（ 1 表?持有，0 表?空倉）乾蛤，然后我們用一個(gè)三維數(shù)組就可以 裝下下面這幾種狀態(tài)的全部組合：

dp[3][2][1] 的含義：今天是第三天每界，現(xiàn)在手上持有股票，最多允許2次交易家卖。

我們想求的最終答案是dp[n-1][K][0]眨层，即最后一天，最多允許K次交易上荡，最多獲得多少利潤趴樱。[0] 表示最終不持有股票馒闷，當(dāng)然比持有股票利潤更大。

二叁征、狀態(tài)轉(zhuǎn)移框架

我們已經(jīng)完成了「狀態(tài)」的窮舉纳账，現(xiàn)在思考每種「狀態(tài)」有哪些「選擇」，應(yīng)該如何更新「狀態(tài)」捺疼。

如果 buy疏虫，就要從利潤中減去 prices[i]，如果 sell啤呼，就要給利潤增加 prices[i]卧秘。并且注意 k 的限制，我們?cè)谶x擇 buy 的時(shí)候媳友，把 k 減小 1斯议，相當(dāng)于剩下可用的交易次數(shù)少 1。

（如果 k 代表當(dāng)前允許交易次數(shù)的話醇锚，隨著買入操作哼御，k應(yīng)該減小，是買入導(dǎo)致了k減小焊唬，所以應(yīng)該是 dp[i][k-1][l] = dp[i-1][k][0] - prices[i]恋昼；而此處 k 代表當(dāng)前已進(jìn)行的交易次數(shù)，所以隨著買入操作赶促，k會(huì)增大液肌。兩種理解都可以，就是狀態(tài)轉(zhuǎn)移方程和base case 里面涉及k的對(duì)應(yīng)修改一下鸥滨。作者這里的解釋和他給的狀態(tài)轉(zhuǎn)移方程對(duì)不上嗦哆，讀者不必糾結(jié)，按這兩種k的理解寫出自己的狀態(tài)轉(zhuǎn)移方程和base case 即可）

這里需要做出更詳細(xì)的解釋婿滓。假設(shè) i = 5老速，那么我們著手畫出它的狀態(tài)轉(zhuǎn)移圖：

好吧，畫不下去了凸主。

原因是：第4天到底是賣出橘券、買入還是休息，取決于目前是否已經(jīng)持有股票卿吐，所以這里分化出了兩棵樹：一棵是當(dāng)前持有旁舰，一棵是當(dāng)前空倉。

而第4天是否持有股票又取決于第3天的持有狀態(tài)及操作嗡官。

當(dāng)沒有買賣次數(shù)的限制條件時(shí)箭窜，上圖的每條路徑都可以走，但當(dāng)有了買賣次數(shù)限制條件 k 時(shí)衍腥，每做 1 次買賣（假設(shè)買時(shí)記 k-1绽快，賣時(shí)k不變）芥丧，k 將減少 1，直到 k=0 時(shí)坊罢，允許的可買賣次數(shù)用盡续担，后面的買路徑就不能再走了，如下圖所示活孩，假如走了綠色的路徑物遇，那紅色的路徑就因?yàn)閗=0不能再買入而走不通了：

（注意，這里的 k 表示當(dāng)前允許的最大買賣次數(shù)）

那么 k 的加入相當(dāng)于幫我們剪掉了某些路徑憾儒，一旦 k = 0询兴，就不能再進(jìn)行買入操作。所以我們每次操作選擇后起趾，還需要維護(hù) k 的狀態(tài)诗舰，但選擇不同的路徑，會(huì)獲得不同的 k 值训裆，也就是 :

dp[0][0]? 第0天眶根，空倉，對(duì)應(yīng)一個(gè) k值為1,

dp[1][0] 第1天边琉，空倉属百，對(duì)應(yīng)一個(gè)k值為1，

dp[1][1] 第1天变姨，持有族扰，對(duì)應(yīng)一個(gè)k值為0，

dp[2][0] 第2天定欧，空倉渔呵，這里就有兩種可能，

????????如果dp[2][0] = dp[1][1] + prices[1]砍鸠，說明第一天持有并賣出扩氢，k = 0

? ? ? ? 如果dp[2][0] = dp[1][0]，說明第一天空倉并休息睦番，k=1

所以 k 與 dp[i][s] 是多對(duì)一關(guān)系类茂，且范圍在 [0,k] 波動(dòng)耍属，所以這些可能性需要新開一個(gè)維度來記錄托嚣，現(xiàn)在dp[i][s] 擴(kuò)展到了 dp[i][k][s]，那么 dp[i][0][s] 代表 k=0時(shí)的dp[i][s]值厚骗，而 dp[i][1][s] 代表 k=1時(shí)的值示启。這里不太容易理解，也就是數(shù)組下標(biāo)對(duì)應(yīng)了 k 的取值领舰，剛好數(shù)組下標(biāo)不能小于0夫嗓。

現(xiàn)在迟螺，我們已經(jīng)完成了動(dòng)態(tài)規(guī)劃中最困難的一步：狀態(tài)轉(zhuǎn)移方程。下面就要定義base case了：

（作者這里的解釋不對(duì)舍咖， k=0意味著不允許交易矩父，但不是利潤為0的原因，雖然不允許交易排霉，但可以繼承前面幾天的利潤對(duì)吧窍株？這里利潤為0是因?yàn)椋x的 k=0 其實(shí)是當(dāng)前已交易次數(shù)攻柠，最大交易次數(shù)是1球订，已交易次數(shù)為0，說明沒有交易過 瑰钮，利潤當(dāng)然是0冒滩；而dp[i][0][1] = -infinity 也不是因?yàn)椴辉试S交易的情況下不可能持有股票，因?yàn)榭梢岳^承過去買入的股票浪谴，雖然不能買入但一直沒有賣出开睡，也是持有股票的對(duì)吧？作者定義的 k=0其實(shí)是當(dāng)前已交易次數(shù)较店，當(dāng)前已交易次數(shù)為0說明不可能已經(jīng)買入士八，所以不可能持有。）

把上面的狀態(tài)轉(zhuǎn)移方程總結(jié)一下：

三梁呈、題目實(shí)戰(zhàn)

? ? 1. 第 I 題婚度，k = 1

k=1 即只允許買賣一次，狀態(tài)轉(zhuǎn)移方程如下（注意作者的 k 表示當(dāng)前已交易次數(shù)）：

（第 i 天官卡，空倉）的狀態(tài)蝗茁，可以從（第 i-1 天，空倉寻咒，第 i 天休息）哮翘、（第 i-1天，持有，第i 天賣出）這兩種途徑達(dá)到。

（第 i 天儿捧，持有）的狀態(tài)浊闪，可以從（第i-1天，持有狞悲，第 i 天休息）、（第 i-1 天，空倉员凝，第 i 天買入）這兩種途徑達(dá)到。

化簡后發(fā)現(xiàn) k 都是 1奋献，即對(duì)狀態(tài)轉(zhuǎn)移方程沒有影響健霹，可以進(jìn)一步簡化：

寫出代碼：

dp[n-1][0] 就是最后一天旺上，空倉時(shí)的總收益。

但 i=0 時(shí)糖埋， dp[i-1] 是越界的宣吱，所以還要對(duì)base case 進(jìn)行處理。

注意今天的狀態(tài)只依賴于昨天的狀態(tài)瞳别，所以用不上整個(gè)dp 數(shù)組凌节，只需要兩個(gè)變量來更新每天的持有、空倉兩個(gè)狀態(tài)即可洒试。

? ? 2. 第 II 題倍奢，k = +INF

·如果 k 為正無窮，可以認(rèn)為 k 和 k-1是一樣的垒棋，可以這樣改寫狀態(tài)轉(zhuǎn)移方程：

代碼如下：

? ? 3. 最佳買賣股票時(shí)機(jī)含冷凍期?卒煞，k = + INF with cooldown

每次賣出后，要等一天才能繼續(xù)交易叼架，只要把這個(gè)特點(diǎn)融入上一題的狀態(tài)轉(zhuǎn)移方程即可：

代碼：

? ? 4. 最佳買賣股票時(shí)機(jī)含手續(xù)費(fèi)畔裕，k = + INF with fee

每次交易要支付手續(xù)費(fèi)，只要把手續(xù)費(fèi)從利潤中減去即可乖订。

代碼：

? ? 5. 第 III 題扮饶，k = 2

由于沒有消除 k的影響，所以必須對(duì) k 進(jìn)行窮舉（循環(huán)）：

其實(shí)這里有點(diǎn)問題乍构，max_k 不一定 小于 n甜无，假如只有2天，max_k = 3哥遮，這樣會(huì)產(chǎn)生非常多的無效計(jì)算：

當(dāng)然這種窮舉不是每個(gè) dp[i][k][s] 都有意義岂丘，比如 dp[0][1][s] 代表第0天只允許再交易1次，但這樣的節(jié)點(diǎn)是不可能存在的眠饮，一開始允許的交易最大次數(shù)是2次奥帘；再者，dp[1][0][s] 也是不可能存在的仪召，因?yàn)閯傔^去一天寨蹋，不可能交易次數(shù)就減少了2。（如下圖示 i扔茅、k與作者的設(shè)定不同已旧，i =0 表示還未開始，i=1才表示第一天咖摹，k=2表示還未買入评姨，k=0表示已買過2次难述，允許購買次數(shù)為0）

由于 k 的取值范圍比較小萤晴，這里還可以直接把 k=1和 k=2的情況全部列出來：

? ? 6. 第 IV 題吐句，K = 給定

有了 K=2 的鋪墊，這題解法應(yīng)該和上一題沒什么區(qū)別店读，但會(huì)超內(nèi)存嗦枢。其實(shí)有效的 K 不應(yīng)該超過 n/2，更進(jìn)一步地屯断，在窮舉過程中文虏，如果 k 表示已交易次數(shù)， k應(yīng)該 不大于 i/2殖演，因?yàn)槊績商熳疃嘟灰滓淮窝趺兀蝗绻?k表示當(dāng)前最大可交易數(shù)，K - k < i/2趴久。

這里代碼只處理了宏觀的情況丸相，即給定的 K 不應(yīng)超過 n/2 的情況，直接當(dāng)成K=INF 來調(diào)用了前面的代碼：

四彼棍、總結(jié)

用一個(gè)狀態(tài)轉(zhuǎn)移方程完成了 6 道股票買賣問題灭忠，其實(shí)不難，但這已經(jīng)屬于動(dòng)態(tài)規(guī)劃問題中較困難的了座硕，我們發(fā)現(xiàn)了三個(gè)狀態(tài)弛作，使用了一個(gè)三維數(shù)組，可以說是三維DP問題了华匾，但解法無非還是窮舉 + 更新映琳。

關(guān)鍵就在于列出所有可能的「狀態(tài)」，然后想想怎么窮舉更新這些「狀態(tài)」蜘拉。一般用一個(gè)多維 dp 數(shù)組存儲(chǔ)這些狀態(tài)刊头，從 base case 開始向后推進(jìn)，推進(jìn)道最后的狀態(tài)诸尽，就是我們想要的答案原杂。

作者這part寫得不是很好，他的思路和如下差不多您机，但沒寫清楚穿肄，有疑惑的朋友可以看下面的（leetcode @千萬利器莫過于信念）：