1. 從“爬樓梯”看動態(tài)規(guī)劃的本質(zhì)1.1 一道題為什么能被力扣列為動態(tài)規(guī)劃入門首選LeetCode 70題 Climbing Stairs爬樓梯常年霸榜在“簡單題”分類里但它的地位卻一點不簡單。幾乎所有刷題攻略、算法課程、面試經(jīng)驗帖都會把這道題放在動態(tài)規(guī)劃的第一站地位和二分查找里的 Binary Search、鏈表里的 Reverse Linked List 差不多。你需要知道的是這道簡單題背后藏著一整套一維動態(tài)規(guī)劃的分析框架把這個框架吃透了后面再做“打家劫舍”“跳躍游戲”“零錢兌換”“最長遞增子序列”這些經(jīng)典題會順暢很多。題目原文其實不復(fù)雜你正在爬樓梯樓梯有 n 階每次可以爬 1 階或 2 階那么到樓頂一共有多少種不同的爬法約束條件里 n 是正整數(shù)。比如 n2 時你可以一次跨 1 階再跨 1 階也可以直接跨 2 階所以答案是 2 種n3 時有 111、12、21 這 3 種。第一次看到這個題的人很容易陷進(jìn)“去枚舉所有爬法”的思路里試圖用遞歸把所有走法列出來。這個方向不算錯但如果你只是想求方案總數(shù)枚舉就繞遠(yuǎn)了。動態(tài)規(guī)劃的思路恰恰相反——它不關(guān)心每一種具體組合長什么樣只關(guān)心“到達(dá)每一階的方案數(shù)”之間存在什么樣的遞推關(guān)系。這種視角的轉(zhuǎn)換就是動態(tài)規(guī)劃和暴力枚舉最本質(zhì)的區(qū)別。1.2 為什么這道題是“一維動態(tài)規(guī)劃”的典型代表動態(tài)規(guī)劃按狀態(tài)的維度分常見的有“一維 DP”和“二維 DP”。一維 DP 通常只需要一個一維數(shù)組甚至幾個變量來存儲狀態(tài)狀態(tài)之間通過一條清晰的遞推關(guān)系串聯(lián)起來二維 DP 則一般涉及兩個維度比如兩個字符串的編輯距離、矩陣路徑問題狀態(tài)一般要開一個二維數(shù)組。Climbing Stairs 是典型的一維 DP狀態(tài)定義就是 dp[i]表示爬到第 i 階樓梯有多少種不同的方法。你只需要維護(hù)這一個數(shù)組不需要第二層維度。它非常適合用來學(xué)“狀態(tài)設(shè)計 狀態(tài)轉(zhuǎn)移方程”這套方法論因為問題足夠簡單不會在理解題意上浪費時間遞推關(guān)系非常直觀可以從實際爬法推導(dǎo)出來不需要高深的數(shù)學(xué)基礎(chǔ)邊界條件少而且明確適合練習(xí)初始化最終代碼量極小但優(yōu)化空間很大從遞歸到記憶化再到數(shù)組滾動思路層層遞進(jìn)。所以如果你剛開始接觸動態(tài)規(guī)劃我強(qiáng)烈建議把這道題作為第一個親手推演、親手寫代碼的樣本。別著急去看別人的題解先自己畫一畫、算一算把“為什么第 i 階的方案數(shù)等于第 i-1 階方案數(shù)加第 i-2 階方案數(shù)”徹底想明白比多刷十道題都值。2. 核心思路拆解從暴力遞歸到遞推公式2.1 先畫一個“遞歸樹”看清問題結(jié)構(gòu)我上手任何一道 DP 題第一件事不是在腦子里套模板而是先手工推演幾個小規(guī)模的例子。以 n5 為例把所有爬法想象成一棵遞歸樹從第 0 階出發(fā)第一步可以爬 1 階到第 1 階也可以爬 2 階到第 2 階到達(dá)第 1 階后又可以選擇再爬 1 階到第 2 階或者再爬 2 階到第 3 階依次類推直到到達(dá)第 5 階。這棵樹往下展開你會發(fā)現(xiàn)很多“子樹”是完全重復(fù)的。比如從第 3 階到第 5 階的爬法無論你是通過哪種途徑到達(dá)第 3 階的后續(xù)的選擇都一樣。這就意味著在暴力枚舉的過程中計算 f(3) 會被反復(fù)執(zhí)行很多次整個算法的耗時呈指數(shù)增長。計算一下遞歸節(jié)的復(fù)雜度如果定義 f(n) 為爬到第 n 階的方案數(shù)那么 f(n) f(n-1) f(n-2)遞歸出口是 f(1)1、f(2)2。這樣遞歸下去函數(shù)調(diào)用次數(shù)大約是 2^n 的規(guī)模。n 稍大一點比如 n40程序就已經(jīng)肉眼可見地卡頓。這不是代碼寫得不好而是算法設(shè)計本身存在大量重復(fù)子問題。2.2 遞推公式的推導(dǎo)為什么是 f(n) f(n-1) f(n-2)這個遞推公式我用一句話說明白你最后一次邁步只有兩種可能要么是從第 n-1 階跨 1 階上來的要么是從第 n-2 階直接跨 2 階上來的。而“爬到第 n-1 階的方案數(shù)”加上“爬到第 n-2 階的方案數(shù)”就是“爬到第 n 階的方案數(shù)”。聽起來像是廢話但它正是動態(tài)規(guī)劃的核心動作把一個規(guī)模較大的問題拆成兩個規(guī)模較小、且結(jié)構(gòu)和原問題完全一致的子問題。這種“原問題和子問題擁有相同性質(zhì)”的特點決定了我們可以使用 DP 來解決而不是另起爐灶重新建模。我建議你自己動手列一下n1只有 1 種直接爬 1 階n2有 2 種11 或直接 2n3從 n1 過來有 f(1)1 種從 n2 過來有 f(2)2 種合計 3 種n4從 n2 過來有 f(2)2 種從 n3 過來有 f(3)3 種合計 5 種n5f(3)f(4)358 種?？吹?1、2、3、5、8 這個數(shù)列對數(shù)列敏感的人馬上會意識到這不就是斐波那契數(shù)列嗎對Climbing Stairs 本質(zhì)上就是斐波那契數(shù)列的翻版只是初始項不同。斐波那契是 F(0)0、F(1)1而本題是 f(1)1、f(2)2。理解這一點后這道題的數(shù)學(xué)底牌就亮出來了但實際工程中我們一般不直接去套斐波那契的通項公式而是仍然用遞推來解決問題因為遞推的時間和空間最容易控制也最容易通過代碼審查。2.3 “動態(tài)規(guī)劃五步法”解決一切 DP 題的心法我刷題這么多年最受用的不是記住某個題的解法而是形成一套固定的分析框架。這里分享一個自己一直在用的“動態(tài)規(guī)劃五步法”每一步都可以對應(yīng)到本題中第一步確定 dp 數(shù)組及下標(biāo)的含義。本題中 dp[i] 表示爬到第 i 階的方法總數(shù)。第二步確定遞推公式。dp[i] dp[i-1] dp[i-2]。這是整個公式體系的核心推導(dǎo)過程前面已經(jīng)講過了。第三步dp 數(shù)組如何初始化。本題的實際含義中dp[1] 11 階樓梯只有 1 種爬法dp[2] 22 階樓梯有 2 種爬法。數(shù)組下標(biāo)從 0 開始的話可以令 dp[0] 1為了讓 dp[2] dp[1] dp[0] 成立。這里有種說法dp[0] 表示“原地不動”也可以理解成一種方案這樣遞推才自洽。有些資料從 dp[0]1 開始這里需要你注意主流題解里用 dp[0]1 或直接跳過 dp[0] 都行但邏輯要自洽最好自己先定好下標(biāo)從 0 開始還是從 1 開始。第四步確定遍歷順序。顯然應(yīng)該從前往后遍歷因為 dp[i] 依賴 dp[i-1] 和 dp[i-2]必須保證在計算 dp[i] 時所依賴的子狀態(tài)已經(jīng)算好了。第五步打印/推演 dp 數(shù)組看是否正常。遇到報錯或者答案不對時把 dp 數(shù)組打印出來和手推的結(jié)果對照是最快的排錯方式。這個方法不僅適用于 Climbing Stairs后面你遇到的所有 DP 題都可以按這個套路來。熟練之后“五步法”會變成你的肌肉記憶看到題目能快速在腦中走完一遍。3. 三種解法橫向?qū)Ρ缺┝f歸、記憶化遞歸、自底向上動態(tài)規(guī)劃3.1 解法一暴力遞歸理解問題但不可用暴力遞歸的代碼非常短但性能極差def climb_stairs_brute(n): if n 2: return n return climb_stairs_brute(n-1) climb_stairs_brute(n-2)時間復(fù)雜度 O(2^n)空間復(fù)雜度 O(n)系統(tǒng)遞歸棧的深度。實際跑起來 n35 的時候已經(jīng)很吃力n45 基本沒法接受。它存在的原因是能讓初學(xué)者快速驗證遞推公式的正確性但工程上毫無意義。不過有一點值得說遞歸版本是“自上而下”的思維。你先想“到達(dá) n 階有多少種”然后拆成“到達(dá) n-1 階”和“到達(dá) n-2 階”一路拆到最小的子問題。這個思維轉(zhuǎn)換在 DP 里叫“遞歸的直覺”是多數(shù)人最容易理解的起點。有了這個起點才能往下一步優(yōu)化。3.2 解法二記憶化遞歸常規(guī)優(yōu)化但空間不夠極致記憶化遞歸的思路很樸素既然暴力遞歸會反復(fù)計算同一個子問題那就用一個數(shù)組把已經(jīng)算過的結(jié)果存下來下次直接用。def climb_stairs_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 2: return n memo[n] climb_stairs_memo(n-1, memo) climb_stairs_memo(n-2, memo) return memo[n]時間復(fù)雜度 O(n)每個子問題只計算一次空間復(fù)雜度 O(n)因為需要一個哈希表或數(shù)組存儲 n 個狀態(tài)再加上遞歸棧。這種方式在實際刷題中經(jīng)常用到它的優(yōu)點是保留了遞歸的直觀結(jié)構(gòu)缺點是在空間上沒有做到最優(yōu)。3.3 解法三自底向上動態(tài)規(guī)劃最推薦的工程寫法自底向上的 DP 是從最小狀態(tài)出發(fā)依次推導(dǎo)到目標(biāo)狀態(tài)。先算 dp[1]、dp[2]再用遞推公式計算 dp[3]一直到 dp[n]。def climb_stairs_dp(n): if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]時間復(fù)雜度 O(n)空間復(fù)雜度 O(n)。這是第一次接觸 DP 的讀者應(yīng)該掌握的版本因為它把“狀態(tài)數(shù)組”這個概念完整暴露了出來方便你對著數(shù)組下標(biāo)和值理解遞推過程。等你完全掌握之后再進(jìn)一步做空間優(yōu)化因為 dp[i] 只依賴前兩個狀態(tài)沒必要保留一整張表直接用兩個變量滾動更新即可。3.4 空間優(yōu)化從 O(n) 到 O(1) 的滾動思想滾動數(shù)組優(yōu)化我覺得是這道題里最妙的一步它體現(xiàn)的思維在后續(xù)很多 DP 題里都會用到def climb_stairs_optimized(n): if n 2: return n prev2, prev1 1, 2 for i in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1這里 prev2 代表 dp[i-2]prev1 代表 dp[i-1]每次循環(huán)把狀態(tài)往前滾動一位?？臻g復(fù)雜度降為 O(1)時間復(fù)雜度仍然是 O(n)。你可能會說內(nèi)存省這一點有什么意義在力扣這種限時受限空間的評測系統(tǒng)里確實意義不大但寫代碼的時候習(xí)慣性地考慮空間優(yōu)化是一個工程師的基本素養(yǎng)。更重要的是滾動數(shù)組思想在“背包問題”“最長回文子串”等高級題目里經(jīng)常出現(xiàn)提前在這道簡單題里培養(yǎng)意識后面會省很多力氣。這里分享一個我在面試現(xiàn)場遇到過的情況候選人能很快寫出 dp 數(shù)組版本但問“能不能把空間壓縮到 O(1)”時卡住了。這道題作為面試開場題面試官往往不只是看你能否 AC更想看你能不能在講清楚復(fù)雜度之后進(jìn)一步優(yōu)化空間。所以我建議你這四種形式都要能手寫出來并且能解釋清楚每一步為什么可以這樣做。3.5 三種方案復(fù)雜度對照速查表為了方便你記憶和復(fù)習(xí)我整理了一張對照表方案時間復(fù)雜度空間復(fù)雜度適用場景暴力遞歸O(2^n)O(n)僅用于理解遞推關(guān)系不用于實際解題記憶化遞歸O(n)O(n)適合保留遞歸思維習(xí)慣時寫面試時也可以提一句自底向上 DPO(n)O(n)入門推薦狀態(tài)清晰方便排錯滾動數(shù)組 DPO(n)O(1)工程和面試最佳選擇需要能熟練寫出來4. 完整實操過程從理解題意到 AC 全流程4.1 動手前的準(zhǔn)備工作邊界條件與規(guī)模預(yù)判在力扣上做題拿到題目后別急著寫代碼。我先檢查幾個要素一是 n 的取值范圍。力扣原題約束是 1 n 45。這個范圍意味著最壞情況時答案是多少提前算一下可以幫你判斷結(jié)果需要用什么類型存儲。當(dāng) n45 時可能的結(jié)果是 1836311903恰好小于 32 位有符號整數(shù)的上限 2147483647所以在 C 中用 int 就夠了Python 則無所謂因為 Python 的 int 是任意精度。但如果你自己改編題目把 n 的范圍擴(kuò)大比如 n100那結(jié)果會變成 573147844013817084101遠(yuǎn)超 64 位整數(shù)范圍。這時候就要考慮大數(shù)類型或用模數(shù)取余了。力扣原題的約束不大但養(yǎng)成先看數(shù)據(jù)范圍、預(yù)估結(jié)果量級的好習(xí)慣能幫你少踩很多坑。二是邊界情況。n1 時直接返回 1 就行n2 時返回 2。很多人在寫 dp[2] 時想當(dāng)然在循環(huán)里統(tǒng)一處理 n1、n2就會出現(xiàn)數(shù)組越界。所以代碼里先判空、先處理邊界是我在每一道題里都堅持做的習(xí)慣。4.2 逐行手寫實現(xiàn)以 Python 和 C 為例先說 Python 版本。剛才已經(jīng)給出了 dp 版本和滾動數(shù)組版本這里我再補(bǔ)充一個我個人在實際刷題中比較喜歡寫的“列表推導(dǎo) 預(yù)分配”的版本class Solution: def climbStairs(self, n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]這個版本的優(yōu)點是結(jié)構(gòu)清晰面試時方便逐步講給面試官聽。你甚至可以一邊講“這是我的 dp 數(shù)組下標(biāo)表示第幾階臺階值表示方法數(shù)”一邊寫出遞推公式整個過程會顯得非常嚴(yán)謹(jǐn)。C 版本同樣簡單class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorint dp(n 1, 0); dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };如果你是在面試中寫 C回答完這個版本后緊接著可以展示“空間優(yōu)化版本”class Solution { public: int climbStairs(int n) { if (n 2) return n; int prev2 1, prev1 2, cur; for (int i 3; i n; i) { cur prev1 prev2; prev2 prev1; prev1 cur; } return prev1; } };大多數(shù)人默認(rèn) Python 寫起來更短但 C 版本也沒有長多少。面試時我建議先寫出 dp 數(shù)組的版本因為你可以在寫的過程中把“為什么 dp[i] dp[i-1] dp[i-2]”講一遍同時看一眼面試官是不是跟得上。等對方點頭了再去主動提空間優(yōu)化這是加分的節(jié)奏。4.3 在力扣上提交的完整流程與踩坑記錄在力扣上提交這道題一般順利但我也見過幾位同學(xué)卡過一些莫名其妙的地方這里統(tǒng)一列一下第一坑數(shù)組長度開成 n 而不是 n1。如果你聲明 vector dp(n)然后訪問 dp[n]直接越界。下標(biāo)從 1 開始使用時記得長度是 n1。類似的問題在 Python 里也一樣[0] * n以后dp[n] 就超出范圍了。第二坑沒有處理 n1 的情況。這里不是說一定會報錯而是當(dāng) n1 時如果你直接給 dp[2] 賦值就先越界了。所以在循環(huán)之前先把if n 2的邊界切斷養(yǎng)成習(xí)慣。第三坑Python 的遞歸寫法超過遞歸深度。有的同學(xué)用lru_cache裝飾器寫記憶化遞歸一切正常但如果直接寫裸遞歸且 n45大概率會報遞歸深度錯誤RecursionError。雖然這個問題在本題的力扣測試集里不一定會出現(xiàn)但平時練習(xí)時最好養(yǎng)成用循環(huán)的習(xí)慣不要把遞歸深度當(dāng)成隱形的坑。第四坑誤用矩陣快速冪。這題確實可以用斐波那契通項公式或矩陣快速冪來解時間復(fù)雜度能到 O(log n)但力扣的 n 上限是 45根本不需要這種優(yōu)化。不過作為擴(kuò)展視野可以了解一下“斐波那契數(shù)列 快速冪”的思路面試時主動講出來會顯得你有廣度。4.4 如何驗證自己寫的代碼是正確的很多初學(xué)者寫完代碼后直接點提交AC 了就萬事大吉。其實更好的做法是在本地先手動驗證幾個值因為提交上去一旦報錯你只知道“答案錯誤”還得回過頭來調(diào)試不如先自測。我常用的一組自測數(shù)據(jù)是n1期望輸出 1n2期望輸出 2n3期望輸出 3n4期望輸出 5n5期望輸出 8n6期望輸出 13。這組數(shù)據(jù)從 1 到 6 恰好是斐波那契數(shù)列從第 2 項開始的連續(xù) 6 個值。跑對了這組基本可以放心提交。如果面試時面試官要求你驗證算法的正確性這個方法也很有說服力因為你展示的不僅是代碼能跑還展示了你對輸入和輸出之間關(guān)系的理解。4.5 從 AC 到深度理解一道題的價值延伸提交通過不等于掌握。很多刷題博主都會講“二刷三刷”的重要性而我認(rèn)為至少做到以下幾點才叫真正“吃透”了 Climbing Stairs能不看答案在 3 分鐘內(nèi)寫出滾動數(shù)組版本能清楚講出“為什么 dp[i] dp[i-1] dp[i-2]”的物理含義能自行擴(kuò)展到“每次可以爬 1、2、3 階”的變體——此時遞推方程變成 dp[i] dp[i-1] dp[i-2] dp[i-3]初始條件相應(yīng)調(diào)整能看懂并講出矩陣快速冪的做法雖然不一定用得上能聯(lián)想到其他一維 DP 題里的類似狀態(tài)轉(zhuǎn)移結(jié)構(gòu)比如“使用最小花費爬樓梯”力扣 746 題。第 3 點很值得你親手做一遍。把步長從 2 改成 3實際上是同一個套路但它能幫你確認(rèn)自己是真的理解了遞推方程的來源而不是死記硬背。第 5 點則是你把單題經(jīng)驗抽象成“一類題”的關(guān)鍵一步。這道題是“加法型”遞推而“打家劫舍”是“選或不選”的決策型遞推結(jié)構(gòu)上很像但狀態(tài)轉(zhuǎn)移的寫法有微妙差異。在題目之間建立聯(lián)系比刷題數(shù)量更重要。5. 常見問題與排錯實錄5.1 輸出斐波那契數(shù)列卻不知道錯在哪有一個很常見的問題有同學(xué)寫完答案后發(fā)現(xiàn)輸出和斐波那契數(shù)列從“0、1、1、2、3、5”對不上就開始懷疑自己代碼寫錯了。其實這里要注意Climbing Stairs 從 f(1)1、f(2)2 開始它其實是斐波那契數(shù)列的“錯位”版本。如果你硬套 Fibonacci 的標(biāo)準(zhǔn)實現(xiàn)F(0)0、F(1)1那么你會發(fā)現(xiàn)標(biāo)準(zhǔn)斐波那契F(0)0, F(1)1, F(2)1, F(3)2, F(4)3, F(5)5本題的答案序列f(1)1, f(2)2, f(3)3, f(4)5, f(5)8。兩者從第 2 項開始關(guān)系是 f(n) F(n1)。所以在代碼實現(xiàn)時不用硬把斐波那契的初始值套進(jìn)來直接按題目語義定義 dp[1] 和 dp[2] 反而更不容易錯。5.2 遞歸超時或棧溢出的排查思路如果你用了遞歸版本去提交力扣給的 n 最大只有 45可能勉強(qiáng)能過也可能超時。如果你改了題目范圍到 100 以上裸遞歸一定會被卡。這時候要先看是不是沒有加記憶化再看遞歸深度是不是太大。Python 的默認(rèn)遞歸深度一般是 1000理論上 n45 不會超過限制但 n 如果擴(kuò)大到 2000就很可能觸發(fā) RecursionError。解決方法是改用循環(huán) DP或者臨時提升遞歸深度限制但這種做法不推薦治標(biāo)不治本。正確的排查順序先確認(rèn)問題規(guī)模再確認(rèn)采用的自上而下還是自下而上最后再想空間優(yōu)化。不要一上來就懷疑環(huán)境問題。5.3 數(shù)組越界和初始化遺漏的快速定位技巧我經(jīng)歷了無數(shù)次 debug 之后總結(jié)出一條簡便經(jīng)驗所有包含 dp 數(shù)組的題目第一件事檢查數(shù)組長度和下標(biāo)的起始位置。如果你從 dp[1] 開始初始化那么數(shù)組長度至少是 n1如果你的循環(huán)變量 i 從 0 開始那 dp[0] 的語義要想清楚。針對這道題最常見的越界發(fā)生在給dp[2]賦值、但數(shù)組長度只有 n 或 n1 時。解決辦法很簡單在一開始就加一個if n 2: return n的守衛(wèi)這個分支能擋掉所有“數(shù)組長度不夠”的問題。5.4 一道變體題的實戰(zhàn)演練為了檢驗?zāi)闶遣皇钦娴恼莆樟撕诵乃悸肺医ㄗh嘗試下面這個變體題目假設(shè)你每次可以爬 1 階或 2 階但不能連續(xù)兩次都跨 2 階。問爬到第 n 階有多少種方法。這個變體一出來一維的普通 dp 數(shù)組就不夠用了因為你必須記住上一步走的是 1 步還是 2 步才能判斷當(dāng)前能否跨 2 階這就得引入二維狀態(tài)上一輪的步長作為第二維。這正是 Climbing Stairs 從“一維 DP”過渡到“帶狀態(tài)約束 DP”的典型例子也是我特別推薦在掌握基礎(chǔ)題后去做的事情在原題上加一個限制看看狀態(tài)定義是否需要調(diào)整。通過這樣的訓(xùn)練你會逐漸理解“狀態(tài)設(shè)計是 DP 的靈魂”這句話。6. 一維動態(tài)規(guī)劃的通用模式不再止步于爬樓梯6.1 從爬樓梯抽出一維 DP 的標(biāo)準(zhǔn)解題模板在吃透 Climbing Stairs 之后我想幫你把它的解題模式抽象成一張“萬能模板”以后遇到新題可以直接套用第一步到第五步第一步提煉狀態(tài)。如果問題可以按某種“階段”劃分比如臺階數(shù)、數(shù)組下標(biāo)、字符串位置往往可以用一維數(shù)組 dp[i] 表示某個階段的最優(yōu)值或方案數(shù)。第二步寫遞推關(guān)系。思考“當(dāng)前階段的最優(yōu)解”怎么從“上一個階段”或“前面幾個階段”推導(dǎo)過來。在 Climbing Stairs 中是從 i-1 和 i-2 兩個階段轉(zhuǎn)移在“使用最小花費爬樓梯”中是從 dp[i-1] 和 dp[i-2] 加上當(dāng)前 cost 轉(zhuǎn)移在“打家劫舍”中是從 dp[i-1]不偷當(dāng)前家和 dp[i-2] nums[i]偷當(dāng)前家轉(zhuǎn)移。第三步處理邊界和初始值。初始狀態(tài)必須能手工算出來至少要把 dp[0] 和 dp[1] 定清楚。第四步確定遍歷順序。一維 DP 絕大多數(shù)是從左到右少數(shù)需要從右到左比如某些背包問題但都是“先算被依賴的狀態(tài)”。第五步考慮優(yōu)化空間。如果 dp[i] 只依賴 dp[i-1]、dp[i-2] 這類常數(shù)個先前狀態(tài)就可以用變量滾動優(yōu)化如果依賴前面所有狀態(tài)比如“最長遞增子序列”里的內(nèi)層循環(huán)那就沒法簡單滾動需要另想辦法。這套流程在面試時非常有用。我見過不少候選人代碼寫得不熟但思路能按這套模板講清楚最終面試評價反而比“悶頭寫對”更高。因為面試官更看重的是你的分析路徑而不是答案本身。6.2 力扣上一維 DP 經(jīng)典題的推薦學(xué)習(xí)順序最后分享一個我的刷題順序建議你想真正把一維動態(tài)規(guī)劃練扎實可以按照下面的順序從易到難推進(jìn)第一步力扣 70 題 Climbing Stairs建立遞推思想 第二步力扣 746 題 Min Cost Climbing Stairs體會“帶成本的狀態(tài)轉(zhuǎn)移” 第三步力扣 198 題 House Robber理解“選或不選”的決策型 DP 第四步力扣 322 題 Coin Change掌握“最值型遞推”和“遍歷所有面值”的套路 第五步力扣 300 題 Longest Increasing Subsequence練習(xí)“雙重循環(huán) 狀態(tài)依賴前面所有狀態(tài)”的進(jìn)階模型。前面兩道簡單題可以一天內(nèi)完成后面三道則需要花點時間推演。但只要你把 Climbing Stairs 的“五步法”練成肌肉記憶后面的每一步都會走得比大多數(shù)人穩(wěn)。我個人刷到 300 題時回頭總結(jié)發(fā)現(xiàn)一維 DP 的高頻考題幾乎都是這些模型的組合或變體極少有跳出這個框架的。所以這題的性價比真的非常高。