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