訓(xùn)練營(yíng)第四十天的題單放在一起群里直接炸了188、309、714三題全是“買賣股票的最佳時(shí)機(jī)”系列的進(jìn)階版。刷到這你會(huì)發(fā)現(xiàn)前面還在講貪心、講普通狀態(tài)轉(zhuǎn)移現(xiàn)在突然要同時(shí)處理交易次數(shù)、冷凍期、手續(xù)費(fèi)三個(gè)額外條件。先別慌這三道題看著嚇人但本質(zhì)上共用同一套動(dòng)態(tài)規(guī)劃模型——如果你搞懂了“股票狀態(tài)機(jī)”這個(gè)思路它們就是同一個(gè)模板換了三次參數(shù)。這篇就按我實(shí)際刷題時(shí)的順序來(lái)聊先解188把“最多k次交易”這個(gè)最通用的模型打通再上309看冷凍期是怎么在狀態(tài)圖里多卡一個(gè)“冷靜”節(jié)點(diǎn)最后是714手續(xù)費(fèi)說(shuō)白了就是在賣出時(shí)多扣一筆錢。順帶會(huì)把初始化、邊界條件、滾動(dòng)數(shù)組這些容易被細(xì)節(jié)絆倒的地方全部攤開講。適合的人群很明確DP已經(jīng)入門、想系統(tǒng)吃透股票專題或者面試前準(zhǔn)備動(dòng)態(tài)規(guī)劃的讀者這篇可以直接當(dāng)復(fù)習(xí)筆記用。1. 三道題放一起刷才能看懂股票DP的套路1.1 從“一次買賣”到“帶約束買賣”遞進(jìn)關(guān)系在哪先盤一下這個(gè)系列在LeetCode上的完整梯度121只能買賣一次122可以無(wú)限次買賣123限制最多兩筆188把123推廣成最多k筆309在無(wú)限次基礎(chǔ)上加了冷凍期714在無(wú)限次基礎(chǔ)上加了手續(xù)費(fèi)。這里有個(gè)很關(guān)鍵的認(rèn)知121、122、123、188是在“交易次數(shù)”這個(gè)維度上遞進(jìn)而309、714是在“交易規(guī)則”上做約束。前者考驗(yàn)?zāi)銓?duì)狀態(tài)維度的抽象能力——從1次擴(kuò)展到2次就能勸退一批人擴(kuò)展到k次更是讓很多人直接寫錯(cuò)數(shù)組大小后者考驗(yàn)?zāi)銓?duì)“額外狀態(tài)”的敏感度——冷凍期本質(zhì)上是給空倉(cāng)狀態(tài)再拆成“能買”和“不能買”兩種手續(xù)費(fèi)則只是在利潤(rùn)計(jì)算時(shí)多一個(gè)減法。把這些題放在同一天刷的價(jià)值就在這里你能清楚地看到所謂的“新題”并不是全新的解題思路而是在同一個(gè)狀態(tài)機(jī)上加點(diǎn)約束。先學(xué)會(huì)畫狀態(tài)轉(zhuǎn)移圖后面所有變體都是在圖里增加節(jié)點(diǎn)或修改邊權(quán)。1.2 股票DP的核心建模方式用狀態(tài)圖代替背公式做股票類DP我的習(xí)慣是永遠(yuǎn)先問(wèn)自己一句話每天交易結(jié)束后我可能處于哪幾種狀態(tài)而不是一上來(lái)就背轉(zhuǎn)移公式。為什么強(qiáng)調(diào)“結(jié)束后”因?yàn)楣善苯灰资前刺彀l(fā)生的你需要在第i天做決策買、賣、還是什么都不干。如果定義成“第i天操作完成后”的狀態(tài)那第i天買入的收益就只依賴第i-1天的狀態(tài)天然規(guī)避了“今天買入今天賣出”這種沒(méi)有意義的閉環(huán)。這個(gè)時(shí)間點(diǎn)的選擇決定了后面所有轉(zhuǎn)移方程是否干凈。用生活話來(lái)說(shuō)你每天早上手里有一筆現(xiàn)金和一筆股票倉(cāng)位一天結(jié)束時(shí)你的資產(chǎn)組合變成什么樣子取決于你今天的操作。dp數(shù)組記錄的就是在不同狀態(tài)下能拿到的最大利潤(rùn)。狀態(tài)有多少種取決于題目給了多少約束有沒(méi)有交易次數(shù)限制有沒(méi)有冷卻期有沒(méi)有手續(xù)費(fèi)。股票DP的所有公式都只是這個(gè)狀態(tài)圖在不同約束下的投影。1.3 為什么這類題刷一道沒(méi)用要三題連刷單刷188你可能學(xué)會(huì)了一個(gè)“奇數(shù)持有、偶數(shù)空倉(cāng)”的數(shù)組技巧但腦子里的模型還是散的只刷309你記住了“賣出后要冷凍一天”但沒(méi)意識(shí)到這只是狀態(tài)圖里多了一個(gè)節(jié)點(diǎn)。三題連在一起你會(huì)發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移這個(gè)事是有肌肉記憶的畫狀態(tài)、寫轉(zhuǎn)移、定初始、算答案永遠(yuǎn)是這四步。更重要的是面試的時(shí)候面試官很喜歡在這個(gè)系列上做組合變化。今天考冷凍期明天可能問(wèn)“手續(xù)費(fèi)改成分段計(jì)費(fèi)”后天可能問(wèn)“最多k筆且?guī)Ю鋬銎凇?。如果你只是背過(guò)某一道題的代碼遇到組合題就廢了但如果你腦子里裝的是“狀態(tài)機(jī)”這個(gè)框架任何新約束都只是在圖上加一筆的事。這也是為什么我強(qiáng)烈建議把這三題當(dāng)成一個(gè)整體來(lái)學(xué)而不是零散地刷。2. 188題k次交易核心是把狀態(tài)數(shù)組“復(fù)制兩份”2.1 狀態(tài)定義把k筆交易拆成2k個(gè)狀態(tài)188題“買賣股票的最佳時(shí)機(jī)IV”題目要求最多完成k筆交易。123題是k2的特例當(dāng)時(shí)用4個(gè)狀態(tài)還能勉強(qiáng)手寫擴(kuò)展到k就必須建立通用的狀態(tài)編號(hào)。我的定義方式是這樣用一維狀態(tài)下標(biāo)j表示當(dāng)前處于“第幾筆交易的什么階段”其中j 0空倉(cāng)還沒(méi)做過(guò)任何交易j 1持有第一筆股票j 2完成第一筆交易空倉(cāng)j 3持有第二筆股票j 4完成第二筆交易空倉(cāng)...規(guī)律很明顯奇數(shù)下標(biāo)代表“持有中”偶數(shù)下標(biāo)代表“空倉(cāng)中”。總共有2k1個(gè)狀態(tài)下標(biāo)從0到2k。為什么要多一個(gè)0因?yàn)樗硎尽皬奈促I入”的初始狀態(tài)這個(gè)狀態(tài)在轉(zhuǎn)移中非常重要確保第1筆買入的金額不會(huì)被錯(cuò)誤累積。持有狀態(tài)和空倉(cāng)狀態(tài)交替出現(xiàn)每次買入讓下標(biāo)加1每次賣出也讓下標(biāo)加1。這樣寫代碼的時(shí)候只需要判斷j的奇偶性就能確定該用哪條轉(zhuǎn)移規(guī)則非常規(guī)整。2.2 轉(zhuǎn)移方程與完整代碼奇數(shù)持有、偶數(shù)空倉(cāng)有了狀態(tài)編號(hào)轉(zhuǎn)移方程就順理成章了。對(duì)于第i天、狀態(tài)j如果j是偶數(shù)空倉(cāng)今天可以繼續(xù)空倉(cāng)也可以從“持有狀態(tài)”賣出。所以 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] prices[i])如果j是奇數(shù)持有今天可以繼續(xù)持有也可以從“空倉(cāng)狀態(tài)”買入。所以 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] - prices[i])唯一需要注意的是j-1不能越界。j0時(shí)沒(méi)有上一個(gè)狀態(tài)它只能繼續(xù)空倉(cāng)所以偶數(shù)狀態(tài)的j0才執(zhí)行買賣邏輯。完整代碼如下class Solution { public: int maxProfit(int k, vectorint prices) { int n prices.size(); if (n 0 || k 0) return 0; // 一筆完整交易至少需要兩天實(shí)際有效交易次數(shù)不會(huì)超過(guò) n / 2 k min(k, n / 2); // 0 ~ 2*k 一共 2*k1 個(gè)狀態(tài) vectorvectorint dp(n, vectorint(2 * k 1, 0)); // 第0天所有奇數(shù)狀態(tài)持有初始化為 -prices[0] for (int j 1; j 2 * k; j 2) { dp[0][j] -prices[0]; } for (int i 1; i n; i) { for (int j 0; j 2 * k; j) { if (j % 2 0) { // 空倉(cāng)狀態(tài) dp[i][j] dp[i - 1][j]; if (j 0) { dp[i][j] max(dp[i][j], dp[i - 1][j - 1] prices[i]); } } else { // 持有狀態(tài) dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); } } } // 最終答案完成最后一筆交易后的空倉(cāng)狀態(tài) return dp[n - 1][2 * k]; } };這個(gè)寫法我在本地跑過(guò)官方測(cè)試用例和題解預(yù)期完全一致。核心就是理解偶數(shù)狀態(tài)用“賣出”轉(zhuǎn)入奇數(shù)狀態(tài)用“買入”轉(zhuǎn)入兩個(gè)方向?qū)?yīng)兩種操作。2.3 k大于n/2時(shí)為什么可以先降級(jí)處理很多人一開始不注意k的取值范圍直接把數(shù)組開成2*k1。如果k很大比如10萬(wàn)而prices只有3天這就會(huì)創(chuàng)建20萬(wàn)列純屬浪費(fèi)。一個(gè)簡(jiǎn)單的數(shù)學(xué)結(jié)論一筆完整的交易至少需要兩天一天買入一天賣出所以n天最多完成n/2筆交易。只要k大于等于n/2實(shí)際約束就失效了等價(jià)于122題的無(wú)限次交易。處理方式就是在dp之前先做一次降級(jí)k min(k, n / 2);這樣數(shù)組大小始終可控。但要注意k0時(shí)要單獨(dú)返回0否則循環(huán)里會(huì)創(chuàng)建只有1列的數(shù)組邏輯上雖然沒(méi)錯(cuò)但沒(méi)必要。2.4 初始化容易翻車第0天所有持有狀態(tài)怎么填第0天的初始化是188題最容易寫錯(cuò)的地方。很多人的第一反應(yīng)是dp[0][1] -prices[0]其他持有狀態(tài)都應(yīng)該是極小值。但在代碼隨想錄的標(biāo)準(zhǔn)寫法里所有奇數(shù)狀態(tài)都直接初始化為-prices[0]。為什么這樣也能對(duì)因?yàn)樵诘?天買入第一筆的最優(yōu)利潤(rùn)就是-prices[0]。對(duì)于“持有第二筆”如果從第1天開始轉(zhuǎn)移它會(huì)被dp[0][2]買入得到而dp[0][2]此時(shí)繼承的是0所以dp[1][3] max(dp[0][3], dp[0][2] - prices[1]) max(-prices[0], -prices[1])。也就是說(shuō)“持有第二筆”的初始資金來(lái)自“完成第一筆”后的空倉(cāng)利潤(rùn)0再買入第二筆——0 - prices[1]是合法的。此時(shí)dp[0][3]-prices[0]雖然從字面上看是“第0天買了第二筆”但在max運(yùn)算里它不會(huì)優(yōu)于未來(lái)真實(shí)的買入操作所以不影響最終結(jié)果。如果還是覺(jué)得別扭你可以把所有奇數(shù)狀態(tài)初始化成 INT_MIN / 2然后在轉(zhuǎn)移時(shí)跳過(guò)非法值。但對(duì)面試來(lái)說(shuō)寫-prices[0]更簡(jiǎn)潔而且只要理解了上面這個(gè)“不變壞”的道理就不會(huì)被面試官問(wèn)倒。3. 309題冷凍期只卡“買入”一條路3.1 冷凍期到底為什么難309題“最佳買賣股票時(shí)機(jī)含冷凍期”規(guī)則是賣出股票后的第二天不能買入。也就是說(shuō)今天賣出明天處于冷卻狀態(tài)不能買后天才能重新買入。難點(diǎn)在于兩狀態(tài)DP持有/不持有在冷凍期規(guī)則下不夠用了。因?yàn)椤安怀钟小庇袃煞N完全不同的情況——一種是可以自由買入一種是昨天剛賣完、今天被迫冷靜。這兩種狀態(tài)對(duì)未來(lái)決策的影響不同可買入狀態(tài)能直接買冷靜狀態(tài)必須再多等一天。所以必須把“不持有”拆成兩個(gè)狀態(tài)。這也是狀態(tài)機(jī)思維的價(jià)值遇到新約束先問(wèn)自己“原有的狀態(tài)分類是否足夠表達(dá)當(dāng)前規(guī)則”。不夠就拆。3.2 三狀態(tài)轉(zhuǎn)移公式與代碼我用三個(gè)狀態(tài)來(lái)表示第i天結(jié)束后的情況狀態(tài)0持有股票狀態(tài)1不持有股票且處于冷凍期也就是今天剛賣出狀態(tài)2不持有股票且不在冷凍期可以自由買入轉(zhuǎn)移邏輯如下?tīng)顟B(tài)0持有今天繼續(xù)持有或者今天從“可自由買入”狀態(tài)買入。注意買入只能從狀態(tài)2來(lái)不能從狀態(tài)1來(lái)因?yàn)闋顟B(tài)1是冷凍期不能買。 dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])狀態(tài)1冷凍期今天不持有且冷凍只可能是昨天持有今天賣出。 dp[i][1] dp[i-1][0] prices[i]狀態(tài)2可買入空倉(cāng)今天不持有也不冷凍可能是昨天就處于冷凍期、今天解凍了也可能昨天本來(lái)就是可買入空倉(cāng)。 dp[i][2] max(dp[i-1][1], dp[i-1][2])代碼class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 0) return 0; // 0: 持有 1: 空倉(cāng)且冷凍 2: 空倉(cāng)且可買 vectorvectorint dp(n, vectorint(3, 0)); dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for (int i 1; i n; i) { dp[i][0] max(dp[i - 1][0], dp[i - 1][2] - prices[i]); dp[i][1] dp[i - 1][0] prices[i]; dp[i][2] max(dp[i - 1][1], dp[i - 1][2]); } // 最后一天持有不如賣出所以答案在狀態(tài)1和狀態(tài)2里 return max(dp[n - 1][1], dp[n - 1][2]); } };用官方示例prices [1,2,3,0,2]跑一遍結(jié)果是3最優(yōu)路徑是第0天買入、第1天賣出賺1然后等第3天買入、第4天賣出賺2。中間第2天處于冷凍期不能買這個(gè)例子把規(guī)則展示得非常直觀。3.3 狀態(tài)壓縮要注意求值順序二維數(shù)組寫對(duì)了之后很多人想優(yōu)化成幾個(gè)變量。這時(shí)候就會(huì)踩一個(gè)經(jīng)典坑直接原地更新后面的狀態(tài)用了被覆蓋過(guò)的舊值。比如有人寫成// 錯(cuò)誤示范 for (int i 1; i n; i) { dp0 max(dp0, dp2 - prices[i]); dp1 dp0_old prices[i]; // 這里的 dp0 已經(jīng)被更新了 dp2 max(dp1_old, dp2); }問(wèn)題在于計(jì)算dp1時(shí)需要的是前一天持有狀態(tài)的舊值但dp0已經(jīng)被今天的值覆蓋了計(jì)算dp2時(shí)需要的是昨天冷凍狀態(tài)的舊值但dp1可能剛被覆蓋。結(jié)果整個(gè)鏈條串味。正確做法是先緩存舊值int hold -prices[0]; // 持有 int cool 0; // 空倉(cāng)且冷凍 int rest 0; // 空倉(cāng)且可買 for (int i 1; i n; i) { int preHold hold, preCool cool, preRest rest; hold max(preHold, preRest - prices[i]); cool preHold prices[i]; rest max(preCool, preRest); } return max(cool, rest);這里每一步用的都是“前一天”的值順序就不再影響正確性。這個(gè)坑在面試手寫代碼時(shí)特別容易暴露我建議刷題階段就把緩存舊值的習(xí)慣養(yǎng)好。3.4 冷凍期加上交易次數(shù)限制怎么擴(kuò)展思路如果面試官在309基礎(chǔ)上追問(wèn)一句“最多k筆且?guī)Ю鋬銎凇辈灰?。思路是讓狀態(tài)多一個(gè)交易次數(shù)的維度dp[i][k][0]表示經(jīng)歷過(guò)k筆交易后持有dp[i][k][1]表示經(jīng)歷過(guò)k筆交易后空倉(cāng)且冷凍dp[i][k][2]表示空倉(cāng)且可買。轉(zhuǎn)移規(guī)則幾乎不變只是買入和賣出時(shí)把k的計(jì)數(shù)變化寫清楚。狀態(tài)圖還是那張狀態(tài)圖只是從二維變成了三維。這就是狀態(tài)機(jī)模型的可擴(kuò)展性。4. 714題手續(xù)費(fèi)本質(zhì)是給“賣出”加負(fù)擔(dān)4.1 手續(xù)費(fèi)放買入還是賣出都行但必須一致714題“買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)”每次交易要付固定手續(xù)費(fèi)fee。核心決策點(diǎn)只有一個(gè)手續(xù)費(fèi)什么時(shí)候從利潤(rùn)里扣除。兩種主流寫法賣出時(shí)扣費(fèi)買入時(shí)只花prices[i]賣出時(shí)到賬prices[i] - fee。買入時(shí)扣費(fèi)買入時(shí)多花fee賣出時(shí)正常到賬prices[i]。兩種寫法最終結(jié)果完全一樣因?yàn)槊抗P交易只會(huì)扣一次費(fèi)用扣在利潤(rùn)的哪一端不影響凈收益。但一定要保持一致不能這邊初始化按買入扣費(fèi)那邊轉(zhuǎn)移又在賣出扣一次那就等于扣了兩次。我習(xí)慣用“賣出時(shí)扣費(fèi)”因?yàn)楦现庇X(jué)買入就是資金流出賣出就是資金流入手續(xù)費(fèi)在流入時(shí)直接扣除不容易漏。4.2 賣出扣費(fèi)版本的完整代碼class Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); if (n 0) return 0; // 0: 空倉(cāng) 1: 持有 vectorvectorint dp(n, vectorint(2, 0)); dp[0][0] 0; dp[0][1] -prices[0]; for (int i 1; i n; i) { // 空倉(cāng)繼續(xù)空倉(cāng)或者從持有狀態(tài)賣出并扣手續(xù)費(fèi) dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i] - fee); // 持有繼續(xù)持有或者從空倉(cāng)狀態(tài)買入 dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; } };如果選買入時(shí)扣費(fèi)初始化和轉(zhuǎn)移改成dp[0][1] -prices[0] - fee; 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);只要保證“每一筆交易只在買入或賣出其中一個(gè)環(huán)節(jié)扣費(fèi)”結(jié)果就不會(huì)有偏差。4.3 大手續(xù)費(fèi)時(shí)為什么也能自動(dòng)“不交易”有一個(gè)非常容易忽略的細(xì)節(jié)如果fee設(shè)置得很大比如prices每天波動(dòng)只有1塊但手續(xù)費(fèi)要10塊最優(yōu)策略是干脆不做任何交易。這個(gè)行為不需要特判DP會(huì)自然給出0。原因在于dp[i][0] max(dp[i-1][0], ...)里的dp[i-1][0]它代表“之前一直空倉(cāng)”的利潤(rùn)0。只要每次賣出的凈利潤(rùn)是負(fù)的max就會(huì)選擇繼續(xù)空倉(cāng)最終答案回到0。我拿prices[1,5,2,8], fee3跑過(guò)最優(yōu)是先1買5賣賺4-31再2買8賣賺6-33總4。如果只看局部第一筆1買2賣利潤(rùn)是-1會(huì)被DP自動(dòng)跳過(guò)。這種“自動(dòng)跳過(guò)虧損交易”的特性是股票DP和貪心的一個(gè)重要區(qū)別也解釋了為什么這類題用DP比貪心更穩(wěn)。4.4 變體討論雙邊收費(fèi)怎么辦如果題目改成“買入和賣出各收一次手續(xù)費(fèi)”本質(zhì)上等價(jià)于每筆交易支付2fee。你只需要把賣出扣的fee改成2fee或者把買入扣和賣出扣同時(shí)保留邏輯完全一致。理解了這個(gè)等價(jià)關(guān)系面試時(shí)不管手續(xù)費(fèi)怎么包裝你都能立刻轉(zhuǎn)化成已知模型。5. 三題連刷的復(fù)盤我發(fā)現(xiàn)股票DP的通用套路5.1 第一步永遠(yuǎn)先畫狀態(tài)轉(zhuǎn)移圖我發(fā)現(xiàn)無(wú)論題目怎么變動(dòng)手寫代碼前花兩分鐘把狀態(tài)圖畫出來(lái)比直接背公式高效得多。所謂“狀態(tài)轉(zhuǎn)移圖”就是用箭頭表示“今天結(jié)束時(shí)的狀態(tài)A經(jīng)過(guò)什么操作可以變成明天結(jié)束時(shí)的狀態(tài)B”。以309為例三狀態(tài)的完整轉(zhuǎn)移關(guān)系是持有態(tài)可以什么都不做繼續(xù)持有也可以賣出進(jìn)入冷凍空倉(cāng)態(tài)。冷凍態(tài)什么都不做下一天變成可買入空倉(cāng)態(tài)?？少I入空倉(cāng)態(tài)可以什么都不做繼續(xù)空倉(cāng)也可以買入進(jìn)入持有態(tài)。把這個(gè)圖畫出來(lái)轉(zhuǎn)移方程就是照著箭頭寫的根本不需要死記。188的狀態(tài)圖則是一串交替的持有/空倉(cāng)節(jié)點(diǎn)買入和賣出就是沿著這串節(jié)點(diǎn)向前走。5.2 第二步明確“當(dāng)天結(jié)束后”的時(shí)間點(diǎn)所有狀態(tài)定義都要統(tǒng)一到“第i天結(jié)束后”。這樣第i天的操作只依賴第i-1天結(jié)束時(shí)的狀態(tài)不會(huì)出現(xiàn)同一天內(nèi)先買后賣、先賣后買的混亂。有人喜歡定義成“第i天操作前”也可以但轉(zhuǎn)移方程會(huì)多出不少邊界判斷。統(tǒng)一用“結(jié)束后”這個(gè)時(shí)間點(diǎn)代碼最干凈復(fù)盤時(shí)也最容易對(duì)照狀態(tài)圖。5.3 第三步判斷狀態(tài)維度能否壓縮188的狀態(tài)數(shù)隨k線性增長(zhǎng)309和714則只需要3個(gè)或2個(gè)狀態(tài)。能壓縮的題目通常有一個(gè)共同特征第i天只依賴第i-1天的值不需要更早的歷史。這時(shí)用幾個(gè)變量或兩行數(shù)組滾動(dòng)即可。但我給個(gè)實(shí)際建議刷題初期先老老實(shí)實(shí)寫二維數(shù)組把邏輯跑通滾動(dòng)數(shù)組作為進(jìn)階優(yōu)化后續(xù)再做。因?yàn)闈L動(dòng)數(shù)組踩的坑舊值覆蓋比二維數(shù)組多得多尤其是309那道題搞錯(cuò)求值順序直接就是WA排查起來(lái)還不好找。5.4 面試時(shí)怎么快速講清楚這類DP如果面試現(xiàn)場(chǎng)遇到股票類DP我的講解順序是固定的先定義狀態(tài)“dp[i][j]表示第i天結(jié)束后處于狀態(tài)j的最大利潤(rùn)。狀態(tài)j分別代表……”然后列出狀態(tài)圖“持有態(tài)可以從……轉(zhuǎn)移來(lái)空倉(cāng)態(tài)可以從……轉(zhuǎn)移來(lái)?！弊詈笳f(shuō)初始化“第0天的合法操作決定了初值第0天買入就是-prices[0]不操作就是0。”復(fù)雜度直接報(bào)O(n狀態(tài)數(shù))狀態(tài)數(shù)通常只有2到3個(gè)188則是O(nk)。這樣講解面試官能立刻看出你是真懂還是背題。尤其是188能說(shuō)清楚“奇數(shù)狀態(tài)從空倉(cāng)買入、偶數(shù)狀態(tài)從持有賣出”這個(gè)規(guī)律比直接甩代碼要有說(shuō)服力得多。6. 踩坑記錄刷這三題時(shí)最容易犯的錯(cuò)6.1 常見(jiàn)問(wèn)題速查表刷完這三題我把容易翻車的點(diǎn)整理成了一張速查表題目典型錯(cuò)誤原因解決辦法188數(shù)組大小寫成2k而不是2k1忘了狀態(tài)0表示“從未交易”下標(biāo)0~2k長(zhǎng)度2k1188k沒(méi)有min(k, n/2)超大k導(dǎo)致內(nèi)存爆炸沒(méi)意識(shí)到完整交易至少兩天dp前先做k min(k, n/2)188第0天奇數(shù)狀態(tài)全部用極小值把第二筆交易的“買入”初始化為不合法用-prices[0]初始化所有奇數(shù)狀態(tài)309狀態(tài)壓縮時(shí)直接原地更新新值覆蓋了舊值導(dǎo)致后一個(gè)狀態(tài)拿到“今天”的數(shù)據(jù)先緩存前一天三個(gè)狀態(tài)再更新309狀態(tài)1和狀態(tài)2的轉(zhuǎn)移寫反沒(méi)搞清楚“今天賣出當(dāng)天算冷凍”狀態(tài)1只由“昨天持有今天賣出”產(chǎn)生714買入扣費(fèi)和賣出扣費(fèi)混用手續(xù)費(fèi)扣了兩次或漏扣統(tǒng)一只在一端扣費(fèi)初始化與之對(duì)應(yīng)714不交易時(shí)答案變成負(fù)數(shù)手續(xù)費(fèi)大于利潤(rùn)時(shí)被迫賣出dp[i][0]從dp[i-1][0]繼承天然規(guī)避6.2 我自己的刷題習(xí)慣我在刷這三題時(shí)習(xí)慣是先把狀態(tài)轉(zhuǎn)移圖寫在紙上再對(duì)照官方題解看自己的狀態(tài)分類和題解是否一致。如果一致再自己寫代碼如果不一致我會(huì)先想明白為什么題解這么分而不是直接抄代碼。三題連刷下來(lái)我最大的感受是股票DP真正難的不是轉(zhuǎn)移公式而是“狀態(tài)劃分”這一步。狀態(tài)劃對(duì)了公式自己就會(huì)冒出來(lái)狀態(tài)劃錯(cuò)后面全亂。6.3 給新手的兩個(gè)自測(cè)小技巧一個(gè)是在LeetCode提交前先用小的樣例手算一遍。比如309用[1,2,3,0,2]這類官方示例714用[1,3,2,8,4,9], fee2這類帶手續(xù)費(fèi)但仍有利潤(rùn)的用例。如果答案能跟手算對(duì)上代碼大概率沒(méi)問(wèn)題。另一個(gè)是檢查邊界n0或n1要直接返回0k0也要返回0。很多WA不是因?yàn)檗D(zhuǎn)移方程錯(cuò)而是邊界條件沒(méi)寫。把這個(gè)習(xí)慣固化下來(lái)之后刷其他DP題也一樣受益。7. 訓(xùn)練營(yíng)第四十天我的刷題節(jié)奏與筆記整理除了這三道題本身我也想聊聊怎么在一個(gè)訓(xùn)練營(yíng)的節(jié)奏里把它們真正消化掉。代碼隨想錄的題單是把同一專題的題集中排布所以第四十天其實(shí)是最好的“歸納整理”時(shí)機(jī)。我的做法是上午先不看題解自己嘗試寫188卡住了就回去翻123的兩筆交易寫法找“從2到k”的共性下午做309和714重點(diǎn)對(duì)比它們和122的差異。晚上把三道題的狀態(tài)定義、轉(zhuǎn)移方程、邊界條件抄在同一頁(yè)筆記上用表格橫向比較。這頁(yè)筆記后來(lái)在我復(fù)習(xí)時(shí)幫了大忙比反復(fù)刷題效率高得多。對(duì)于第一次接觸股票DP的讀者我的建議是不要試圖一天內(nèi)完全理解所有細(xì)節(jié)。先能獨(dú)立寫出188的二維DP再給309加上第三個(gè)狀態(tài)最后給714加上手續(xù)費(fèi)每一步都跑通官方用例。這樣拆開練第四十天這個(gè)節(jié)點(diǎn)才能真正把“股票系列”轉(zhuǎn)化為自己的東西。最后分享一個(gè)小技巧把三道題的狀態(tài)定義壓縮成一句話——“先想清楚每天交易結(jié)束后有哪幾種狀態(tài)再畫箭頭最后寫轉(zhuǎn)移公式”。這句口訣我后來(lái)在面試?yán)镉眠^(guò)好幾次都能很快理清思路。股票DP并沒(méi)有傳說(shuō)中那么玄它只是把“狀態(tài)復(fù)用”這件事做到了極致而已。