今天接著刷代碼隨想錄算法訓練營第四十天內容是三道買賣股票系列的變式題188買賣股票的最佳時機IV、309最佳買賣股票時機含冷凍期、714買賣股票的最佳時機含手續(xù)費。這三道題放在一起很有講究它們把基礎的股票動態(tài)規(guī)劃又向外推了一大步一個加了交易次數限制一個加了冷卻期約束一個加了手續(xù)費成本。對訓練營刷到這里的人來說前幾天的121、122、123應該已經打下了底子今天這三道題的核心已經不是“會不會寫狀態(tài)轉移”而是能不能把狀態(tài)設計想清楚。很多人在刷這三道題時最大的感受是公式看著都能懂一關掉題解自己寫就翻車。原因在于買賣股票這類題目的狀態(tài)定義高度抽象尤其是188這種帶k次限制的題目狀態(tài)數量直接翻倍初始化也容易出問題。這篇博客就按我自己的刷題思路把這三道題從狀態(tài)設計、遞推推導到滾動數組優(yōu)化、常見坑位完整拉一遍希望能給正在卡這些題的同學一點參考。1. 三道題為什么值得放在一起刷先說結論121、122、123三題是“單次買賣、無限買賣、兩次買賣”到了188、309、714約束條件就不再是“次數”這一個維度了。188是把123推廣到“最多k次”考驗的是能不能用統(tǒng)一的狀態(tài)下標把交易次數編碼進去309引入冷凍期相當于在“賣出”和“下一次買入”之間強行插入一個冷卻時間714則是在每次交易利潤中固定扣掉一筆手續(xù)費讓“是不是值得賣”變成了一個需要考慮成本的問題。這三道題放在第四十天這個時間點實際上是動態(tài)規(guī)劃專題里“狀態(tài)機DP”的一次集中訓練。所謂狀態(tài)機DP通俗講就是把一筆錢在賬戶里的形態(tài)拆成“持有股票”和“持有現金”這兩種狀態(tài)再把題目里的限制條件轉化成狀態(tài)之間的轉移規(guī)則。所有股票類題目本質上都是在同一個骨架下改狀態(tài)數量和轉移邊。這三道題一刷完再回去看121、122、123你會覺得之前那些特判都是某種更通用模型的簡化版。所以這篇文章我不會只貼題解代碼而是把每一步狀態(tài)為什么要這么設計、初始化為什么是那串數字、滾動數組為什么順序要對盡量都說清楚。2. 188. 買賣股票的最佳時機IV把k次交易拆成2k個狀態(tài)這一題幾乎所有人第一反應都是123題最多兩筆交易我用四個狀態(tài)硬編碼那k筆交易我是不是得循環(huán)建狀態(tài)思路對但實現上有幾個細節(jié)非常容易被忽略。2.1 為什么k次交易不能直接套用貪心無限次交易的122題可以用貪心因為每一段上漲的利潤都可以獨立收割不用記錄交易次數。但一旦限定了“最多k筆”貪心就失效了你沒法判斷當前這一筆賣出之后剩余的交易次數還夠不夠覆蓋后面更大的漲幅。所以必須用動態(tài)規(guī)劃而且狀態(tài)里必須攜帶“已經完成了多少筆交易”的信息。最簡單粗暴的做法是dp[i][j][t]三維分別表示天數、持股狀態(tài)、已完成交易次數但這樣代碼寫起來啰嗦內存也浪費。188題的經典做法是用下標本身來編碼交易次數。2.2 狀態(tài)設計奇數位持有偶數位空倉我直接用一維數組解釋因為理解了它二維數組只是多了天數下標而已。設dp[j]表示當前天數結束后的某個狀態(tài)j的取值范圍是0到2kj 0空倉且一筆交易都沒做過j 1持有股票且這是第一筆交易的買入階段j 2空倉且已經完成第一筆交易j 3持有股票且這是第二筆交易的買入階段j 4空倉且已經完成第二筆交易以此類推規(guī)律非常明顯奇數下標代表“當前持有股票”偶數下標代表“當前空倉”而下標數值剛好編碼了已經進行到第幾次交易。j 2k是最終狀態(tài)即完成k筆交易后的最大現金。這個設計的巧妙之處在于不需要額外開一個維度去記錄交易次數交易次數被隱含在狀態(tài)下標里。2.3 遞推公式的完整推導對于每個新的一天價格price[i]到來后我們要決定“保持原狀”還是“從上一狀態(tài)轉換過來”。先看奇數下標j持有狀態(tài)dp[j] max(dp[j], dp[j - 1] - price[i])dp[j]保持原值表示昨天就持有今天繼續(xù)持有dp[j - 1] - price[i]表示昨天處于空倉狀態(tài)已完成上一次賣出今天買入進入持有狀態(tài)再看偶數下標j空倉狀態(tài)dp[j] max(dp[j], dp[j - 1] price[i])dp[j]保持原值表示昨天就空倉今天繼續(xù)空倉dp[j - 1] price[i]表示昨天持有股票今天賣出賺取差價后回到空倉狀態(tài)注意一個細節(jié)j從0到2k依次遞增j - 1一定是剛好的對偶狀態(tài)。比如j2空倉j-11持有這是一對完整的“買入→賣出”路徑。j4空倉j-13持有這是第二對。所以循環(huán)里不需要分類討論第幾筆交易只需要判斷奇偶。2.4 初始化到底是什么意思第一天的初始化經常有人寫錯。第0天dp[0] 0空倉且什么都沒做所有奇數下標dp[1] dp[3] dp[5] ... -price[0]所有偶數下標除了0dp[2] dp[4] ... 0為什么第二天還沒到第二筆買入狀態(tài)就設為-prices[0]因為可以理解為第一天先完成了一筆“買賣同價”的零利潤交易然后又立刻買入。比如價格10先買入10再賣出10現金不變然后再買入10現金為-10這個操作完全合法且不影響利潤。用它作為狀態(tài)初值后續(xù)第二筆、第三筆交易才能正常轉移。如果你把dp[3]初始化為極小值意味著強制認為第二天之前不可能有第二筆買入那遇到“第一天就大跌、第二天就大漲”的用例就會漏答案。最穩(wěn)的做法就是奇數位統(tǒng)一初始化為-prices[0]。2.5 一維滾動數組和從后往前的遍歷順序二維寫法空間是O(n*k)一維滾動可以壓到O(k)。但有個關鍵點更新一維dp時必須從后往前遍歷j。原因不復雜。比如更新dp[2]時需要用到dp[1]的“昨天”值如果j從小到大更新dp[1]已經被今天的price更新過了那dp[2]用的就是“今天買入后”的dp[1]相當于在一天之內連續(xù)做了“買入→賣出→再買入”雖然同價買賣的邊距為0不會讓答案變大但為了和二維遞推嚴格對齊習慣上還是從大到小遍歷保證每個狀態(tài)引用的都是前一天舊值。完整代碼class Solution { public int maxProfit(int k, int[] prices) { int n prices.length; if (n 0 || k 0) { return 0; } // 關鍵剪枝n天最多完成n/2次完整交易 k Math.min(k, n / 2); int[] dp new int[2 * k 1]; // 奇數位初始化為第一天的買入價 for (int j 1; j 2 * k; j 2) { dp[j] -prices[0]; } for (int i 1; i n; i) { for (int j 2 * k; j 1; j--) { if ((j 1) 1) { // 持有狀態(tài)保持 或 從空倉買入 dp[j] Math.max(dp[j], dp[j - 1] - prices[i]); } else { // 空倉狀態(tài)保持 或 從持有賣出 dp[j] Math.max(dp[j], dp[j - 1] prices[i]); } } } return dp[2 * k]; } }時間復雜度是O(n*k)空間是O(k)。2.6 k值的剪枝數學解釋每天最多只能完成一筆買入加一筆賣出而一筆完整交易至少需要兩天所以n天最多完成n/2次完整交易。題目給的k如果大于n/2其實可以剪枝為n/2否則dp數組浪費空間而且白白增加循環(huán)次數。這個剪枝不是可選項是性能優(yōu)化里的必要一步。我一開始沒剪枝在某些大k用例直接超時剪完立刻通過。3. 309. 最佳買賣股票時機含冷凍期三個狀態(tài)比四個更好理解309這題剛上手的時候很容易把狀態(tài)分成“持有”和“不持有”兩個然后在賣出后加一天冷卻。但實際上兩個狀態(tài)不夠因為“不持有”分成了兩種完全不同含義的情況處于冷卻期不能買和不在冷卻期可以買。所以正確做法是拆成三個狀態(tài)。3.1 冷凍期如何改變狀態(tài)圖如果題目沒有冷凍期持有和空倉兩個狀態(tài)互相轉來轉去就行。加了冷凍期以后從“賣出”這個動作出來必須先在“冷凍”狀態(tài)停留一天才能回到“可買入”狀態(tài)。也就是說狀態(tài)轉換圖變成一條鏈表持有股票 → 賣出 → 冷凍期 → 可買入 → 買入 → 持有股票這也解釋了為什么不能像122那樣簡單地貪心如果某一天剛賣出第二天即使出現更低價格也不能立刻買貪心的“回補”邏輯直接失效。3.2 三個狀態(tài)的定義設dp[i][0]為第i天結束后持有股票的最大利潤dp[i][1]為第i天結束后不持有股票且處于冷凍期的最大利潤dp[i][2]為第i天結束后不持有股票且不在冷凍期的最大利潤。這里最重要的主觀提醒是“冷凍期”指的是賣出當天結束后開始計算第二天不能買入。所以處于dp[i][1]狀態(tài)的人就是今天剛剛賣出明天被禁止買入。3.3 遞推公式逐條看第一條dp[i][0] max(dp[i - 1][0], dp[i - 1][2] - prices[i])保持不變昨天就持有今天繼續(xù)持有買入昨天不持有且不在冷凍期今天才能買入第二條dp[i][1] dp[i - 1][0] prices[i]這一條是直接賦值不是max。因為只有一種途徑進入冷凍期昨天持有今天賣出。不存在“昨天冷凍期今天接著冷凍”的情況冷凍期只有一天。第三條dp[i][2] max(dp[i - 1][1], dp[i - 1][2])昨天處于冷凍期今天解除冷凍可以買入昨天就不在冷凍期今天繼續(xù)保持可買入狀態(tài)為什么必須要有這一條因為dp[i][1]只代表今天剛賣出的人如果昨天是冷凍期今天已經自動恢復成可買狀態(tài)這個狀態(tài)必須歸屬于dp[i][2]否則第二天買入時找不到正確的來源。3.4 初始化的細節(jié)處理初始化常見困惑就是dp[0][1]到底設多少。第一天結束時不可能處于冷凍期因為沒有股票可賣但習慣上把它設為0。可以理解為第一天虛擬地做了一次不賺不虧的買賣然后進入冷凍期或者直接解釋為“不可能狀態(tài)設為0不會影響最終答案”。我更推薦一個嚴謹一點的說法dp[0][1]0等價于“買入且賣出同一支股票利潤為0”這種虛擬狀態(tài)不會污染后續(xù)max運算反而讓代碼簡單。完整代碼class Solution { public int maxProfit(int[] prices) { int n prices.length; if (n 0) { return 0; } int[][] dp new int[n][3]; dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]); dp[i][1] dp[i - 1][0] prices[i]; dp[i][2] Math.max(dp[i - 1][1], dp[i - 1][2]); } return Math.max(dp[n - 1][1], dp[n - 1][2]); } }最后返回時不能取dp[n-1][0]因為最后一天還持有股票明顯不是最優(yōu)解。需要在“剛賣出處于冷凍期”和“空倉可買”兩個狀態(tài)里取最大值。3.5 空間壓縮為三個滾動變量如果只想開O(1)空間可以用三個變量交替滾動。這里有個容易踩坑的點必須用臨時變量保存舊值。int hold -prices[0]; int cool 0; int free 0; for (int i 1; i n; i) { int newHold Math.max(hold, free - prices[i]); int newCool hold prices[i]; int newFree Math.max(free, cool); hold newHold; cool newCool; free newFree; } return Math.max(cool, free);newFree不能直接用舊的free更新后再算newHold因為如果free先變成了“今天才解除冷凍”的狀態(tài)那今天就不能再用來買入邏輯順序上就亂了。這種細小的順序問題在筆試里特別容易讓人栽跟頭建議手工模擬一遍就理解了。4. 714. 買賣股票的最佳時機含手續(xù)費貪心和DP都能通過714相比前兩題其實更簡單但它是三題里最適合練“把成本建模進狀態(tài)”的題目。手續(xù)費帶來一個顯著變化有些看似上漲的小波段去掉手續(xù)費后反而虧錢所以不能無腦賺差價。4.1 手續(xù)費扣在哪一步更合理手續(xù)費可以設置在買入時也可以設置在賣出時。只要整道題統(tǒng)一只扣一次最終結果是一樣的。習慣上放在賣出時更容易理解賣出后錢變多但每筆交易要扣除固定手續(xù)費。設置一個狀態(tài)定義dp[i][0]第i天結束后持有股票的最大利潤dp[i][1]第i天結束后不持有股票的最大利潤轉移公式dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]) dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee)第一個式子表示保持持有或買入第二個式子表示保持空倉或賣出時扣手續(xù)費。4.2 DP寫法class Solution { public int maxProfit(int[] prices, int fee) { int n prices.length; if (n 2) { return 0; } int[][] dp new int[n][2]; dp[0][0] -prices[0]; dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee); } return dp[n - 1][1]; } }這個寫法是最穩(wěn)妥的也不容易錯。如果面試時間緊直接上DP版基本不會翻車。4.3 貪心解法的理解難度在于buy的更新規(guī)則714有一個比DP短很多的貪心寫法我第一次看到時根本不敢信因為利潤是拆成一段一段累加的。核心思路是用buy維護“當前買入成本含手續(xù)費”只要價格高于成本就賣出然后把buy更新為當前價格如果后續(xù)遇到更低的價格再重新設定買入成本。class Solution { public int maxProfit(int[] prices, int fee) { int n prices.length; if (n 2) { return 0; } int buy prices[0] fee; int profit 0; for (int i 1; i n; i) { if (prices[i] buy) { profit prices[i] - buy; buy prices[i]; } else if (prices[i] fee buy) { buy prices[i] fee; } } return profit; } }這個版本里buy第一次是“價格手續(xù)費”的買入門檻。當價格高于buy時賣出利潤是prices[i] - buy但賣出后buy被更新成prices[i]而不是prices[i]fee。很多人不理解這一步為什么再次買入不收手續(xù)費了我的理解是每次真正賣出時手續(xù)費已經通過“prices[i] - buy”中的buy扣除了一次。賣出后更新buy為當前價相當于假設自己在賣出當天重新買入如果第二天繼續(xù)上漲后續(xù)累積的利潤是純粹的上漲差價不需要再重復扣手續(xù)費。這樣一段連續(xù)上漲的所有利潤總和等于“最終賣價 - 最初買價 - 一次手續(xù)費”跟一筆完成交易的結果一致。如果遇到prices[i]fee比當前buy還便宜說明出現了一個明顯更優(yōu)的買入點這時更新buy為prices[i]fee相當于拋棄之前一段還沒賣出的持倉重新掛一個新的買入單。這個貪心寫法效率很高時間復雜度O(n)空間O(1)。但它的正確性依賴對buy更新的精確理解如果沒吃透筆試現場容易把自己繞暈。我建議先寫DP版保底等有時間再嘗試貪心。4.4 兩種解法怎么選DP版適用范圍更廣擴展性強比如后續(xù)如果再疊加冷凍期或交易次數限制DP版只需要改狀態(tài)轉移而貪心版基本要重寫。貪心版勝在常數小、代碼短理解透了在面試里能加分。我個人的習慣是如果面試官明確要最優(yōu)時間空間再寫貪心否則用DP。5. 三題對比、常見誤區(qū)與通用套路三題刷完我試著把它們放在一張表里對比能更直觀看到區(qū)別題目狀態(tài)數量額外限制時間復雜度空間復雜度核心難點188 買賣股票IV2k1最多k筆交易O(n*k)O(k)用狀態(tài)下標編碼交易次數309 含冷凍期3賣出后隔一天才能買O(n)O(1)正確拆分“不持有”語義714 含手續(xù)費2每筆交易扣手續(xù)費O(n)O(1)手續(xù)費建模與貪心更新規(guī)則三題共同的內核是把資金形態(tài)抽象成“持有股票”和“持有現金”兩類限制條件轉成狀態(tài)轉移的邊。188限制的是邊的數量309限制的是“賣出到買入”邊的延遲714則是給賣出邊加了一個負權重。5.1 最容易踩的三個坑第一個坑是188不剪枝k值。k如果大于n/2dp數組長度會很大循環(huán)次數也翻倍在大數據用例下會超時。先用kMath.min(k, n/2)剪枝這是很多題解不會特意強調但很重要的細節(jié)。第二個坑是309的dp狀態(tài)定義不清。如果把不持有籠統(tǒng)當一個狀態(tài)買入時就分不清昨天是否在冷凍期導致錯誤答案。必須分成“冷凍期”和“可買”兩個狀態(tài)記住冷凍期只會停留一天dp[i][1]只能由賣出轉移而來。第三個坑是714的滾動數組或貪心的更新時間不對。如果用一維DP滾動賣出狀態(tài)先更新持有狀態(tài)再更新會讓同一天里賣出又買入產生額外的虛擬交易。穩(wěn)妥做法是用臨時變量存舊狀態(tài)或者直接用二維數組。5.2 狀態(tài)機DP的通用解題框架我把三道題放進同一個框架里代碼隨想錄里也強調過動態(tài)規(guī)劃五部曲這兩者是統(tǒng)一的確定有哪些狀態(tài)把所有可能的賬戶狀態(tài)列全寧多勿少明確狀態(tài)之間可以怎么轉移畫一下狀態(tài)轉移表哪些邊存在、哪些邊禁止根據轉移表寫遞推公式初始化邊界狀態(tài)打印dp數組驗證遇到新題先想這一步不要一上來套模板。比如以后遇到帶n天冷卻期、或者手續(xù)費隨持有時間變化的變式只需要修改轉移邊和成本公式其他框架完全不變。5.3 一點刷題體會之前刷123題的時候四狀態(tài)硬編碼讓我覺得股票DP是道“背模板題”但188一出來模板瞬間不夠用了。真正幫到我的不是背公式而是把狀態(tài)圖畫出來標注哪條邊能走哪條邊不能走再去寫遞推。309和714都是在畫圖之后一下就通了。如果你現在也在訓練營刷到這里建議別急著把所有題解背下來先花十分鐘在這三道題的狀態(tài)圖上畫一畫尤其是309那個三狀態(tài)閉環(huán)畫完再寫代碼會順手很多。最后再說一個小技巧提交不過先別急著看題解把dp數組打出來逐行對比第一天的初始化有沒有異常很多時候答案就藏在初始化的數字里。