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