規(guī)劃：從遞歸到滾動數組的完整優(yōu)化路徑)
1. 為什么一道“簡單題”能穩(wěn)坐Hot 100前70名爬樓梯LeetCode 70在Hot 100榜單里幾乎是必刷的存在。題目描述極其樸素每次可以爬1級或2級臺階問爬到第n級有多少種不同的方法。很多第一次刷到的人會覺得這題太簡單了小學奧數都講過斐波那契。但它在面試里出現的頻率一直居高不下因為這道題考察的不是你背沒背過遞推公式而是你對遞歸、記憶化搜索、動態(tài)規(guī)劃、空間優(yōu)化、數學推導這一整套算法思維鏈條的掌握程度。先說題目本身。假設你站在地面上要上到第n級臺階。你每一步只能跨1級或者2級。問總共有多少種不同的走法。這個問題為什么是斐波那契邏輯其實很簡單要到達第n級臺階你最后一步只可能是從第n-1級跨1級上來或者從第n-2級跨2級上來。那么到達第n級的方法數 到達第n-1級的方法數 到達第n-2級的方法數。邊界條件n1時只有1種走法跨1級n2時有2種走法11或直接跨2級。所以 f(n) f(n-1) f(n-2)f(1)1f(2)2。這就是斐波那契數列的原型只是初值從1,1變成了1,2。Hot 100把它放在比較靠前的位置我推測是因為它既是動態(tài)規(guī)劃入門的最佳標本又隱藏著多種優(yōu)化路徑。從最原始的遞歸到帶備忘錄的遞歸再到自底向上的動態(tài)規(guī)劃再到滾動數組壓縮空間再到通項公式和矩陣快速冪這道題可以循序漸進地串起至少五層解法。而且每一層解法都對應著面試中可能被追問的問題——你還能優(yōu)化嗎時間復雜度是多少空間復雜度呢這些追問在真實面試里幾乎一定會出現。跟很多“背模板”的題目不同爬樓梯的每一種解法都有清晰的推導路徑不存在“這個狀態(tài)定義我看不懂”這類問題。它適合作為動態(tài)規(guī)劃的第一個完整案例來研究。2. 從遞歸到動態(tài)規(guī)劃一條完整的算法進階鏈路這一節(jié)我想把爬樓梯的五種典型解法全部過一遍。重點不是讓你記住代碼而是理解每一步的動機為什么一開始要寫遞歸遞歸為什么慢備忘錄解決了什么動態(tài)規(guī)劃又改進了什么2.1 純遞歸最直觀但最糟糕的寫法如果完全按照遞推公式翻譯寫出來的代碼非常簡潔def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)這段代碼能跑但n一大就徹底卡死。n45時在普通機器上可能要跑幾十秒甚至更久。原因在于它把同一個子問題重復計算了無數次。舉個例子計算f(5)需要計算f(4)和f(3)計算f(4)又需要計算f(3)和f(2)。也就是說f(3)被重復計算了兩次f(2)被重復計算了更多次。如果畫一棵遞歸樹這棵樹上有大量重疊的子樹而每一棵子樹都被完全重算。f(5)這棵遞歸樹的節(jié)點數大約是15個f(10)遞歸樹的節(jié)點數大約是177個f(20)大約是21891個。這個增長速度是指數級的準確說是 O(2^n)。在LeetCode上提交純遞歸版本n稍微大一點就會超時這幾乎是必然的。注意n45已經是斐波那契的一個臨界點了再往上數值會超過32位整數范圍。在LeetCode題目默認約束里n最大就到45也是為了避免在純算法層面引入大數處理的問題。但現實中很多題目會要求對10^97取模那n就可以給到很大。2.2 備忘錄遞歸用空間消滅重復計算既然重復計算是罪魁禍首那最簡單的優(yōu)化思路就是把已經算過的結果存起來下次直接用。這就是備忘錄遞歸Memoization。def climbStairs(n: int) - int: memo {} def dfs(x: int) - int: if x 2: return x if x in memo: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)也可以用數組當備忘錄因為n是連續(xù)的整數用列表比用字典更節(jié)省開銷def climbStairs(n: int) - int: memo [0] * (n 1) memo[1], memo[2] 1, 2 def dfs(x: int) - int: if memo[x] ! 0: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)這里有一個容易踩的小坑memo數組初始化長度為n1因為我們需要訪問下標n。memo[0]在這個題目里用不到但數組占位時給它留一個位置是標準做法。如果你把數組長度寫成n那么當n恰好等于1或2時memo[n]就會越界。備忘錄遞歸把時間復雜度從O(2^n)降到了O(n)。因為每個子問題只計算一次計算f(n)最多需要計算f(1)到f(n)共n個子問題?？臻g復雜度也是O(n)用來存memo數組。這里有必要解釋一個關鍵點遞歸是“自頂向下”的。我們從f(n)出發(fā)不斷向下分解到f(1)、f(2)然后再把結果一層層返回上來。備忘錄只是保證了過程中不重復計算但遞歸調用棧本身仍然存在最深的調用深度是n。2.3 自底向上DP從基態(tài)出發(fā)一步一個腳印備忘錄遞歸雖然已經不超時了但遞歸函數調用本身有開銷而且在極端情況下還有爆棧風險n10000時遞歸深度就可能出問題不過這道題n只有45。更工程化的寫法是自底向上的動態(tài)規(guī)劃。def climbStairs(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]理解自底向上DP的核心在于狀態(tài)定義和轉移方程狀態(tài)定義dp[i]表示爬到第i級臺階有多少種方法。轉移方程dp[i] dp[i-1] dp[i-2]。初始化dp[1]1dp[2]2。為什么需要這兩行的初始化因為遞推公式在i1和i2時沒有前驅項。dp[1]只有“跨1級”這一條路徑dp[2]有“11”和“直接跨2級”兩條路徑這些是人工推出來的基態(tài)也是一切遞推的起點。從實現角度講這個版本的時間復雜度仍是O(n)但省掉了遞歸的函數調用開銷而且是迭代執(zhí)行不會爆棧?？臻g復雜度還是O(n)因為dp數組把所有中間結果都存了。2.4 復雜度對比一次看清每層優(yōu)化解法時間復雜度空間復雜度關鍵點純遞歸O(2^n)O(n)遞歸棧重疊子問題大量重復計算備忘錄遞歸O(n)O(n)用緩存消除重復仍保留遞歸棧自底向上DPO(n)O(n)迭代計算無遞歸棧開銷滾動數組O(n)O(1)只保留前兩個狀態(tài)通項公式O(log n)或O(1)按浮點算O(1)數學降維但有精度問題矩陣快速冪O(log n)O(1)泛化能力強適合大n場景在實際面試中從純遞歸開始說起然后一路優(yōu)化到滾動數組這是一條非常標準的“展示你懂動態(tài)規(guī)劃”的路徑。面試官想看的不是你直接背出最優(yōu)解而是你有沒有能力一層層發(fā)現問題、提出改進。3. 滾動數組的奇妙之處其實根本不需要記住所有臺階從自底向上DP的代碼可以看到當我們在計算dp[i]時真正用到的只有dp[i-1]和dp[i-2]。dp[0]、dp[3]、dp[4]這些比i-2更早的值在后續(xù)計算中永遠不會再被訪問。這就引出了一個顯而易見的空間優(yōu)化思路用兩個變量滾動維護前兩個狀態(tài)即可沒必要開一個長度為n1的數組。def climbStairs(n: int) - int: if n 2: return n prev2 1 # dp[1] prev1 2 # dp[2] for i in range(3, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1這個版本的執(zhí)行過程是這樣的初始prev21表示第1級的方法數prev12表示第2級的方法數。計算第3級cur 2 1 3。更新prev22prev13。計算第4級cur 3 2 5。更新prev23prev15。以此類推計算完第n級后prev1就是答案。代碼細節(jié)上要注意變量的更新順序必須先讓prev2接收舊的prev1再讓prev1接收cur。如果順序反過來prev2會被寫成cur那下一步計算時prev2就不再是dp[i-2]了。這個細節(jié)是滾動數組最容易寫錯的地方我就見過很多人面試時當場翻車。在Python里其實還有一種更優(yōu)雅的寫法def climbStairs(n: int) - int: a, b 1, 2 for _ in range(2, n): a, b b, a b return b if n 1 else a這段代碼利用了Python的元組賦值特性右邊的b和ab都是在賦值前先取值所以不會出現上面說的更新順序問題。但如果你用的是Java或C就得老老實實按變量交換的順序寫。為什么滾動數組在這里成立深層原因是這個DP的狀態(tài)轉移只依賴前兩個狀態(tài)它是一個“階數固定為2”的遞推。如果把問題改成“每次可以爬1到k階”那計算dp[i]就需要依賴前k個狀態(tài)滾動數組就得開一個長度為k的環(huán)形緩沖而不是只用兩個變量。把這道題的滾動數組寫法理解透徹之后你會發(fā)現它對后續(xù)很多DP題都有啟發(fā)——比如“不同路徑II”里的二維矩陣逐行滾動本質上也是同一個思路當前狀態(tài)只依賴鄰近的若干個歷史狀態(tài)其他的一概不需要留。4. 從數學視角降維打擊通項公式和矩陣快速冪如果說滾動數組是把空間壓到了極致那通項公式和矩陣快速冪就是在時間復雜度上做文章。這兩種方法在n較小的時候體現不出優(yōu)勢甚至代碼更復雜、更容易出錯但在n極大比如10^18的競賽場景下它們是唯一能跑的方案。4.1 斐波那契通項公式的實戰(zhàn)價值爬樓梯的遞推式和斐波那契幾乎一樣只是初值不同。標準斐波那契是F(0)0F(1)1爬樓梯是f(1)1f(2)2。如果平移一下下標可以證明 f(n) F(n1)其中F是標準斐波那契數列。因此爬樓梯的通項公式可以直接從斐波那契通項公式導出f(n) (1 / sqrt(5)) * [((1 sqrt(5)) / 2)^(n1) - ((1 - sqrt(5)) / 2)^(n1)]用代碼實現import math def climbStairs(n: int) - int: sqrt5 math.sqrt(5) phi (1 sqrt5) / 2 psi (1 - sqrt5) / 2 return int(round((phi ** (n 1) - psi ** (n 1)) / sqrt5))這個方法在理論上時間復雜度是O(log n)——因為冪運算可以用快速冪——空間O(1)。但實際使用時要非常小心浮點精度問題。當n較大時phi^n和psi^n都是極大的浮點數相減之后除以sqrt5再四舍五入可能會因為浮點誤差得到錯誤的整數結果。LeetCode上這道題的n最大到45浮點精度還夠用但如果n到70以上這個公式就可能翻車。所以我的建議是通項公式知道原理即可筆試面試中不要主動用。它屬于看起來優(yōu)雅、用起來扎手的方案。除非題目明確要求O(log n)且n極大否則滾動數組才是最優(yōu)選擇。4.2 矩陣快速冪把一個遞推改寫成一個冪運算如果說通項公式是碰巧斐波那契才有封閉解那矩陣快速冪就是一套普適性更強的通用方法。它適用于任何線性遞推關系在n巨大的時候依然可以在O(log n)時間內求解。思路是把遞推關系表示成矩陣形式[f(n) ] [1 1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)]也就是說[f(n) ] [1 1]^(n-2) [f(2)] [f(n-1)] [1 0] [f(1)]然后問題轉化為計算矩陣的n-2次冪。矩陣冪運算可以用快速冪二進制拆分做到O(log n)。def climbStairs(n: int) - int: if n 2: return n def mat_mul(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def mat_pow(mat, power): result [[1, 0], [0, 1]] # 單位矩陣 while power 0: if power 1: result mat_mul(result, mat) mat mat_mul(mat, mat) power 1 return result base [[1, 1], [1, 0]] result mat_pow(base, n - 2) # 乘以初始向量 [f(2), f(1)] [2, 1] return result[0][0] * 2 result[0][1] * 1矩陣快速冪在實際面試中算是加分項。大多數候選人能說到滾動數組就已經很好了如果你能主動補充“如果n達到10^18滾動數組也扛不住可以用矩陣快速冪或者通項公式”面試官會認為你對復雜度的理解是系統(tǒng)的而不是只會背模板。這道題最經典的面試走位就是先答滾動數組O(n)/O(1)再補一句矩陣快速冪可以到O(log n)配合追問給出推導。不過要提醒一句面試中如果你決定寫矩陣快速冪必須確保矩陣乘法函數完全正確。這類代碼有一堆下標細節(jié)非常容易寫錯。我自己在練習時至少寫錯過三次都是因為a[0][0]*b[0][0]這類交叉項弄混。4.3 到底該記哪些解法一個務實的取舍我不建議把五種解法全部背下來。真正值得反復手寫的是自底向上DP理解狀態(tài)定義和轉移滾動數組面試中最優(yōu)的時空平衡矩陣快速冪作為知識儲備能推導能講清即可純粹遞歸是理解用的不是讓你寫在卷子上的。通項公式知道存在即可面試主動提它反而可能被追問到精度問題得不償失。5. 面試官通常怎么圍繞這道題做文章爬樓梯在面試中的表現有點特殊。它難嗎不難。但正因為它不難面試官可以在這道題上做大量擴展和追問考察你的思維深度。常見的追問路徑我都遇到過總結下來有這么幾類。5.1 遞推公式的推導過程很多候選人上來就背“dp[i] dp[i-1] dp[i-2]”但被問“為什么”就卡住了。其實推導只需要一句話到第i級的最后一步要么從第i-1級跨1級要么從第i-2級跨2級這兩種情況互不重疊所以相加。這個“最后一步分類”的思想是動態(tài)規(guī)劃領域最核心的建模方式。幾乎所有一維DP都可以套這個模板最后一步有哪些選擇每種選擇對應哪種前序狀態(tài)把選擇對應的方案數加起來。5.2 邊界情況面試官會問n0時是多少n1呢n2呢題目本身默認n是正整數所以n0不需要處理。但如果你自己把代碼寫成“dp[0]1, dp[1]1”也能得到正確答案因為這樣本質上就是從斐波那契數列F(1)1, F(2)2換了一種初始化方式。這不算錯但解釋起來比較繞。如果你采用dp[0]1的寫法必須能清楚解釋dp[0]代表什么——很多人的解釋是“站在原地有一種方法就是不動”這個解釋在數學上是自洽的但在直覺上比較牽強。所以我個人還是推薦用dp[1]1, dp[2]2這種邊界設置語義更直觀。5.3 大數取模變種如果n被放大到10^18所有O(n)的解法都會超時必須用矩陣快速冪。同時結果要對10^97取模。這種變體在筆試里經常出現但LeetCode原題不會。刷題時建議自己練一遍取模版矩陣快速冪因為取模運算如果放錯了位置非常容易產生負數和溢出。5.4 擴展問題“每次可以跨1或2或3階呢”如果允許一次跨1、2、3階遞推式就變成f(n) f(n-1) f(n-2) f(n-3)初值也要相應擴展到f(1)1, f(2)2, f(3)4。這個擴展考察的不是新的算法而是你能不能舉一反三把狀態(tài)轉移方程的維度從2改成3。再往外擴一層如果“每次最多可以跨k階”就需要維護一個長度為k的滑動窗口和。這一步已經不是單純套公式能解決的了而是要分析區(qū)間和的前綴優(yōu)化。這一道題可以一直延伸到面試結束根本用不著面試官再出新題。6. 爬樓梯可不是孤立的它是一整個DP入門家族的核心很多人刷完爬樓梯就急著往后面的中等題、困難題沖我覺得有點浪費。爬樓梯這一題延伸出去的變種其實是動態(tài)規(guī)劃入門階段性價比最高的一組訓練。我自己帶過幾個新人都是讓他們把這組題吃透再往后走效果比盲目刷題好得多。6.1 最小花費爬樓梯爬樓梯的Cost版劍指Offer 10-II和LeetCode 746都涉及“最小花費爬樓梯”。題目變成每一級臺階都有一個cost[i]你可以從第0級或第1級出發(fā)跨1級或2級問到達樓頂的最小花費。這題的建模思路和爬樓梯完全一致只不過狀態(tài)從“方案數”變成了“最小花費”轉移也從加法變成了取mindp[i] cost[i] min(dp[i-1], dp[i-2])最后答案是min(dp[n-1], dp[n-2])——因為可以從倒數第一級或倒數第二級跨到樓頂。它和爬樓梯放在一起刷能讓你清晰感受到DP的兩大基本問題類型計數型和最值型。計數型用加法因為每個方案都是獨立的最值型用min或者max因為只需要保留最優(yōu)路徑。6.2 不同路徑從一維到二維的跨越LeetCode 62“不同路徑”是爬樓梯的二維版。一個機器人在m x n網格的左上角每次只能向下或向右走一步問到達右下角有多少條路徑。狀態(tài)定義從dp[i]變成dp[i][j]轉移方程從dp[i] dp[i-1] dp[i-2]變成dp[i][j] dp[i-1][j] dp[i][j-1]。沒有本質區(qū)別只是多了一個維度。但很多人第一次接觸二維DP時會覺得變了個物種其實不然。建議在刷完爬樓梯之后立刻刷這一題你會感覺一切都很順。6.3 爬樓梯的k階推廣滑動窗口優(yōu)化如果題目改成“每次可以爬1到k階”那么f(n) f(n-1) f(n-2) ... f(n-k)直接計算的話時間復雜度是O(nk)。如果k和n都很大比如n10^6k10^5就需要用前綴和或者滑動窗口來優(yōu)化。設sum[i] f(1) f(2) ... f(i)那么f(n) sum[n-1] - sum[n-k-1]。這樣每個f(n)都可以O(1)算出來整體降到O(n)。這是從爬樓梯這題延伸出去的一個不錯的進階點難度剛剛好不會讓人勸退但又確實需要動點腦筋。6.4 三步問題面試題庫里的孿生兄弟還有一個高頻變體叫“三步問題”也就是一次可以跨1、2、3階n可能到10^6要求對10^97取模。這個題比LeetCode原版更接近筆試實戰(zhàn)因為涉及了模運算。它的核心坑有兩個取模后相加可能要取兩次模f(n) (f(n-1) f(n-2) f(n-3)) % MOD取模不能改變中間態(tài)的精度所以每一步都要模踩過幾次之后你會形成一個條件反射看到“結果可能很大”立刻想到模運算看到n的范圍大過10^7立刻想到矩陣快速冪或者O(1)數學解。7. 我把這題的所有坑都踩了一遍給你整理一份避坑清單7.1 語言差異導致的溢出陷阱LeetCode原題n最大45結果在32位有符號整數范圍內2^31-1約21億而f(45)是1836311903剛好沒爆。但如果你用的是C的intf(46)就已經溢出變成負數了。所以很多C選手刷題時會把返回值類型寫成long long這個習慣是好的因為題目一旦擴展int根本扛不住。Java的int是32位long是64位但很多國內筆試場景為了防止溢出會要求輸出對10^97取模。如果你沒有養(yǎng)成取模的習慣那就得格外小心輸入范圍。python不存在這個問題Python的int是任意精度的這算是刷題時一個隱性優(yōu)勢但也容易讓人忽視溢出這個考點——面試問Java/C溢出問題時就會露餡。7.2 循環(huán)邊界range(3, n1)還是range(2, n)滾動數組寫法里循環(huán)邊界特別容易出錯。我用的是for i in range(3, n 1):當n3時循環(huán)會執(zhí)行一次算出f(3)。當n4時循環(huán)會執(zhí)行兩次先算f(3)再算f(4)。這個邊界寫對了答案就是對的。把n1寫成n的話n3就算不到f(3)直接返回錯誤的prev12。如果要精簡成a, b 1, 2 for _ in range(2, n): a, b b, a b return b if n 1 else a當n3時range(2, 3)只循環(huán)一次此時a2, b3返回b3正確。當n2時循環(huán)不執(zhí)行b2返回2正確。這種寫法可以少寫一個if分支但前提是你要理解range的終點是開區(qū)間。7.3 遞歸的返回值陷阱如果你寫備忘錄遞歸而且要處理n0的邊界那么if n 2: return n這個條件的n2包含了n0返回0。但如果你把條件寫成n1或n2分別return那就必須在函數入口先處理n0否則遞歸到n0時memo[0]可能沒初始化或者直接越界。7.4 面試中的“由淺入深”節(jié)奏最后說一個比較玄學但很重要的點面試時怎么講這道題決定了面試官對你的印象。我建議的答題節(jié)奏是四步走先確認題目邊界問清楚n的范圍和是否要求取模。說出最直觀的遞歸思路并主動指出它的指數級復雜度問題。緊接著給出DP解法并解釋狀態(tài)轉移是怎么從“最后一步”推導出來的。最后說“這個狀態(tài)轉移只依賴前兩項所以可以用兩個變量滾動優(yōu)化到O(1)空間”然后直接寫下最終代碼。這套流程下來面試官能看到你完整的思維鏈路而不是一個只會默寫答案的刷題機器。如果你還有余力可以補充一句“如果n極大可以用矩陣快速冪優(yōu)化到O(log n)”這就是錦上添花。我個人在刷這題時最大的體會是好題的評判標準不在于難而在于能不能用最簡單的外殼裝下整個算法體系的骨架。爬樓梯顯然就是這樣的題。你在這題上花兩個小時把每一層解法的來龍去脈都弄明白收益遠大于草草刷三四個不同題型的題。對了還有一個很容易被忽略的小細節(jié)LeetCode的題解區(qū)很多人喜歡寫“完全背包解法”把爬樓梯看成無限物品的完全背包。這個視角本身沒問題但是對于剛入門DP的新手我建議先不要把思路搞復雜。先把一維DP的基本模型吃透背包的視角等做到完全背包專題的時候再回頭來看你會發(fā)現原來這些題在更高維度上是相通的。 爬樓梯與動態(tài)規(guī)劃：從遞歸到滾動數組的完整優(yōu)化路徑
1. 為什么一道“簡單題”能穩(wěn)坐Hot 100前70名爬樓梯LeetCode 70在Hot 100榜單里幾乎是必刷的存在。題目描述極其樸素每次可以爬1級或2級臺階問爬到第n級有多少種不同的方法。很多第一次刷到的人會覺得這題太簡單了小學奧數都講過斐波那契。但它在面試里出現的頻率一直居高不下因為這道題考察的不是你背沒背過遞推公式而是你對遞歸、記憶化搜索、動態(tài)規(guī)劃、空間優(yōu)化、數學推導這一整套算法思維鏈條的掌握程度。先說題目本身。假設你站在地面上要上到第n級臺階。你每一步只能跨1級或者2級。問總共有多少種不同的走法。這個問題為什么是斐波那契邏輯其實很簡單要到達第n級臺階你最后一步只可能是從第n-1級跨1級上來或者從第n-2級跨2級上來。那么到達第n級的方法數 到達第n-1級的方法數 到達第n-2級的方法數。邊界條件n1時只有1種走法跨1級n2時有2種走法11或直接跨2級。所以 f(n) f(n-1) f(n-2)f(1)1f(2)2。這就是斐波那契數列的原型只是初值從1,1變成了1,2。Hot 100把它放在比較靠前的位置我推測是因為它既是動態(tài)規(guī)劃入門的最佳標本又隱藏著多種優(yōu)化路徑。從最原始的遞歸到帶備忘錄的遞歸再到自底向上的動態(tài)規(guī)劃再到滾動數組壓縮空間再到通項公式和矩陣快速冪這道題可以循序漸進地串起至少五層解法。而且每一層解法都對應著面試中可能被追問的問題——你還能優(yōu)化嗎時間復雜度是多少空間復雜度呢這些追問在真實面試里幾乎一定會出現。跟很多“背模板”的題目不同爬樓梯的每一種解法都有清晰的推導路徑不存在“這個狀態(tài)定義我看不懂”這類問題。它適合作為動態(tài)規(guī)劃的第一個完整案例來研究。2. 從遞歸到動態(tài)規(guī)劃一條完整的算法進階鏈路這一節(jié)我想把爬樓梯的五種典型解法全部過一遍。重點不是讓你記住代碼而是理解每一步的動機為什么一開始要寫遞歸遞歸為什么慢備忘錄解決了什么動態(tài)規(guī)劃又改進了什么2.1 純遞歸最直觀但最糟糕的寫法如果完全按照遞推公式翻譯寫出來的代碼非常簡潔def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)這段代碼能跑但n一大就徹底卡死。n45時在普通機器上可能要跑幾十秒甚至更久。原因在于它把同一個子問題重復計算了無數次。舉個例子計算f(5)需要計算f(4)和f(3)計算f(4)又需要計算f(3)和f(2)。也就是說f(3)被重復計算了兩次f(2)被重復計算了更多次。如果畫一棵遞歸樹這棵樹上有大量重疊的子樹而每一棵子樹都被完全重算。f(5)這棵遞歸樹的節(jié)點數大約是15個f(10)遞歸樹的節(jié)點數大約是177個f(20)大約是21891個。這個增長速度是指數級的準確說是 O(2^n)。在LeetCode上提交純遞歸版本n稍微大一點就會超時這幾乎是必然的。注意n45已經是斐波那契的一個臨界點了再往上數值會超過32位整數范圍。在LeetCode題目默認約束里n最大就到45也是為了避免在純算法層面引入大數處理的問題。但現實中很多題目會要求對10^97取模那n就可以給到很大。2.2 備忘錄遞歸用空間消滅重復計算既然重復計算是罪魁禍首那最簡單的優(yōu)化思路就是把已經算過的結果存起來下次直接用。這就是備忘錄遞歸Memoization。def climbStairs(n: int) - int: memo {} def dfs(x: int) - int: if x 2: return x if x in memo: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)也可以用數組當備忘錄因為n是連續(xù)的整數用列表比用字典更節(jié)省開銷def climbStairs(n: int) - int: memo [0] * (n 1) memo[1], memo[2] 1, 2 def dfs(x: int) - int: if memo[x] ! 0: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)這里有一個容易踩的小坑memo數組初始化長度為n1因為我們需要訪問下標n。memo[0]在這個題目里用不到但數組占位時給它留一個位置是標準做法。如果你把數組長度寫成n那么當n恰好等于1或2時memo[n]就會越界。備忘錄遞歸把時間復雜度從O(2^n)降到了O(n)。因為每個子問題只計算一次計算f(n)最多需要計算f(1)到f(n)共n個子問題?？臻g復雜度也是O(n)用來存memo數組。這里有必要解釋一個關鍵點遞歸是“自頂向下”的。我們從f(n)出發(fā)不斷向下分解到f(1)、f(2)然后再把結果一層層返回上來。備忘錄只是保證了過程中不重復計算但遞歸調用棧本身仍然存在最深的調用深度是n。2.3 自底向上DP從基態(tài)出發(fā)一步一個腳印備忘錄遞歸雖然已經不超時了但遞歸函數調用本身有開銷而且在極端情況下還有爆棧風險n10000時遞歸深度就可能出問題不過這道題n只有45。更工程化的寫法是自底向上的動態(tài)規(guī)劃。def climbStairs(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]理解自底向上DP的核心在于狀態(tài)定義和轉移方程狀態(tài)定義dp[i]表示爬到第i級臺階有多少種方法。轉移方程dp[i] dp[i-1] dp[i-2]。初始化dp[1]1dp[2]2。為什么需要這兩行的初始化因為遞推公式在i1和i2時沒有前驅項。dp[1]只有“跨1級”這一條路徑dp[2]有“11”和“直接跨2級”兩條路徑這些是人工推出來的基態(tài)也是一切遞推的起點。從實現角度講這個版本的時間復雜度仍是O(n)但省掉了遞歸的函數調用開銷而且是迭代執(zhí)行不會爆棧?？臻g復雜度還是O(n)因為dp數組把所有中間結果都存了。2.4 復雜度對比一次看清每層優(yōu)化解法時間復雜度空間復雜度關鍵點純遞歸O(2^n)O(n)遞歸棧重疊子問題大量重復計算備忘錄遞歸O(n)O(n)用緩存消除重復仍保留遞歸棧自底向上DPO(n)O(n)迭代計算無遞歸棧開銷滾動數組O(n)O(1)只保留前兩個狀態(tài)通項公式O(log n)或O(1)按浮點算O(1)數學降維但有精度問題矩陣快速冪O(log n)O(1)泛化能力強適合大n場景在實際面試中從純遞歸開始說起然后一路優(yōu)化到滾動數組這是一條非常標準的“展示你懂動態(tài)規(guī)劃”的路徑。面試官想看的不是你直接背出最優(yōu)解而是你有沒有能力一層層發(fā)現問題、提出改進。3. 滾動數組的奇妙之處其實根本不需要記住所有臺階從自底向上DP的代碼可以看到當我們在計算dp[i]時真正用到的只有dp[i-1]和dp[i-2]。dp[0]、dp[3]、dp[4]這些比i-2更早的值在后續(xù)計算中永遠不會再被訪問。這就引出了一個顯而易見的空間優(yōu)化思路用兩個變量滾動維護前兩個狀態(tài)即可沒必要開一個長度為n1的數組。def climbStairs(n: int) - int: if n 2: return n prev2 1 # dp[1] prev1 2 # dp[2] for i in range(3, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1這個版本的執(zhí)行過程是這樣的初始prev21表示第1級的方法數prev12表示第2級的方法數。計算第3級cur 2 1 3。更新prev22prev13。計算第4級cur 3 2 5。更新prev23prev15。以此類推計算完第n級后prev1就是答案。代碼細節(jié)上要注意變量的更新順序必須先讓prev2接收舊的prev1再讓prev1接收cur。如果順序反過來prev2會被寫成cur那下一步計算時prev2就不再是dp[i-2]了。這個細節(jié)是滾動數組最容易寫錯的地方我就見過很多人面試時當場翻車。在Python里其實還有一種更優(yōu)雅的寫法def climbStairs(n: int) - int: a, b 1, 2 for _ in range(2, n): a, b b, a b return b if n 1 else a這段代碼利用了Python的元組賦值特性右邊的b和ab都是在賦值前先取值所以不會出現上面說的更新順序問題。但如果你用的是Java或C就得老老實實按變量交換的順序寫。為什么滾動數組在這里成立深層原因是這個DP的狀態(tài)轉移只依賴前兩個狀態(tài)它是一個“階數固定為2”的遞推。如果把問題改成“每次可以爬1到k階”那計算dp[i]就需要依賴前k個狀態(tài)滾動數組就得開一個長度為k的環(huán)形緩沖而不是只用兩個變量。把這道題的滾動數組寫法理解透徹之后你會發(fā)現它對后續(xù)很多DP題都有啟發(fā)——比如“不同路徑II”里的二維矩陣逐行滾動本質上也是同一個思路當前狀態(tài)只依賴鄰近的若干個歷史狀態(tài)其他的一概不需要留。4. 從數學視角降維打擊通項公式和矩陣快速冪如果說滾動數組是把空間壓到了極致那通項公式和矩陣快速冪就是在時間復雜度上做文章。這兩種方法在n較小的時候體現不出優(yōu)勢甚至代碼更復雜、更容易出錯但在n極大比如10^18的競賽場景下它們是唯一能跑的方案。4.1 斐波那契通項公式的實戰(zhàn)價值爬樓梯的遞推式和斐波那契幾乎一樣只是初值不同。標準斐波那契是F(0)0F(1)1爬樓梯是f(1)1f(2)2。如果平移一下下標可以證明 f(n) F(n1)其中F是標準斐波那契數列。因此爬樓梯的通項公式可以直接從斐波那契通項公式導出f(n) (1 / sqrt(5)) * [((1 sqrt(5)) / 2)^(n1) - ((1 - sqrt(5)) / 2)^(n1)]用代碼實現import math def climbStairs(n: int) - int: sqrt5 math.sqrt(5) phi (1 sqrt5) / 2 psi (1 - sqrt5) / 2 return int(round((phi ** (n 1) - psi ** (n 1)) / sqrt5))這個方法在理論上時間復雜度是O(log n)——因為冪運算可以用快速冪——空間O(1)。但實際使用時要非常小心浮點精度問題。當n較大時phi^n和psi^n都是極大的浮點數相減之后除以sqrt5再四舍五入可能會因為浮點誤差得到錯誤的整數結果。LeetCode上這道題的n最大到45浮點精度還夠用但如果n到70以上這個公式就可能翻車。所以我的建議是通項公式知道原理即可筆試面試中不要主動用。它屬于看起來優(yōu)雅、用起來扎手的方案。除非題目明確要求O(log n)且n極大否則滾動數組才是最優(yōu)選擇。4.2 矩陣快速冪把一個遞推改寫成一個冪運算如果說通項公式是碰巧斐波那契才有封閉解那矩陣快速冪就是一套普適性更強的通用方法。它適用于任何線性遞推關系在n巨大的時候依然可以在O(log n)時間內求解。思路是把遞推關系表示成矩陣形式[f(n) ] [1 1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)]也就是說[f(n) ] [1 1]^(n-2) [f(2)] [f(n-1)] [1 0] [f(1)]然后問題轉化為計算矩陣的n-2次冪。矩陣冪運算可以用快速冪二進制拆分做到O(log n)。def climbStairs(n: int) - int: if n 2: return n def mat_mul(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def mat_pow(mat, power): result [[1, 0], [0, 1]] # 單位矩陣 while power 0: if power 1: result mat_mul(result, mat) mat mat_mul(mat, mat) power 1 return result base [[1, 1], [1, 0]] result mat_pow(base, n - 2) # 乘以初始向量 [f(2), f(1)] [2, 1] return result[0][0] * 2 result[0][1] * 1矩陣快速冪在實際面試中算是加分項。大多數候選人能說到滾動數組就已經很好了如果你能主動補充“如果n達到10^18滾動數組也扛不住可以用矩陣快速冪或者通項公式”面試官會認為你對復雜度的理解是系統(tǒng)的而不是只會背模板。這道題最經典的面試走位就是先答滾動數組O(n)/O(1)再補一句矩陣快速冪可以到O(log n)配合追問給出推導。不過要提醒一句面試中如果你決定寫矩陣快速冪必須確保矩陣乘法函數完全正確。這類代碼有一堆下標細節(jié)非常容易寫錯。我自己在練習時至少寫錯過三次都是因為a[0][0]*b[0][0]這類交叉項弄混。4.3 到底該記哪些解法一個務實的取舍我不建議把五種解法全部背下來。真正值得反復手寫的是自底向上DP理解狀態(tài)定義和轉移滾動數組面試中最優(yōu)的時空平衡矩陣快速冪作為知識儲備能推導能講清即可純粹遞歸是理解用的不是讓你寫在卷子上的。通項公式知道存在即可面試主動提它反而可能被追問到精度問題得不償失。5. 面試官通常怎么圍繞這道題做文章爬樓梯在面試中的表現有點特殊。它難嗎不難。但正因為它不難面試官可以在這道題上做大量擴展和追問考察你的思維深度。常見的追問路徑我都遇到過總結下來有這么幾類。5.1 遞推公式的推導過程很多候選人上來就背“dp[i] dp[i-1] dp[i-2]”但被問“為什么”就卡住了。其實推導只需要一句話到第i級的最后一步要么從第i-1級跨1級要么從第i-2級跨2級這兩種情況互不重疊所以相加。這個“最后一步分類”的思想是動態(tài)規(guī)劃領域最核心的建模方式。幾乎所有一維DP都可以套這個模板最后一步有哪些選擇每種選擇對應哪種前序狀態(tài)把選擇對應的方案數加起來。5.2 邊界情況面試官會問n0時是多少n1呢n2呢題目本身默認n是正整數所以n0不需要處理。但如果你自己把代碼寫成“dp[0]1, dp[1]1”也能得到正確答案因為這樣本質上就是從斐波那契數列F(1)1, F(2)2換了一種初始化方式。這不算錯但解釋起來比較繞。如果你采用dp[0]1的寫法必須能清楚解釋dp[0]代表什么——很多人的解釋是“站在原地有一種方法就是不動”這個解釋在數學上是自洽的但在直覺上比較牽強。所以我個人還是推薦用dp[1]1, dp[2]2這種邊界設置語義更直觀。5.3 大數取模變種如果n被放大到10^18所有O(n)的解法都會超時必須用矩陣快速冪。同時結果要對10^97取模。這種變體在筆試里經常出現但LeetCode原題不會。刷題時建議自己練一遍取模版矩陣快速冪因為取模運算如果放錯了位置非常容易產生負數和溢出。5.4 擴展問題“每次可以跨1或2或3階呢”如果允許一次跨1、2、3階遞推式就變成f(n) f(n-1) f(n-2) f(n-3)初值也要相應擴展到f(1)1, f(2)2, f(3)4。這個擴展考察的不是新的算法而是你能不能舉一反三把狀態(tài)轉移方程的維度從2改成3。再往外擴一層如果“每次最多可以跨k階”就需要維護一個長度為k的滑動窗口和。這一步已經不是單純套公式能解決的了而是要分析區(qū)間和的前綴優(yōu)化。這一道題可以一直延伸到面試結束根本用不著面試官再出新題。6. 爬樓梯可不是孤立的它是一整個DP入門家族的核心很多人刷完爬樓梯就急著往后面的中等題、困難題沖我覺得有點浪費。爬樓梯這一題延伸出去的變種其實是動態(tài)規(guī)劃入門階段性價比最高的一組訓練。我自己帶過幾個新人都是讓他們把這組題吃透再往后走效果比盲目刷題好得多。6.1 最小花費爬樓梯爬樓梯的Cost版劍指Offer 10-II和LeetCode 746都涉及“最小花費爬樓梯”。題目變成每一級臺階都有一個cost[i]你可以從第0級或第1級出發(fā)跨1級或2級問到達樓頂的最小花費。這題的建模思路和爬樓梯完全一致只不過狀態(tài)從“方案數”變成了“最小花費”轉移也從加法變成了取mindp[i] cost[i] min(dp[i-1], dp[i-2])最后答案是min(dp[n-1], dp[n-2])——因為可以從倒數第一級或倒數第二級跨到樓頂。它和爬樓梯放在一起刷能讓你清晰感受到DP的兩大基本問題類型計數型和最值型。計數型用加法因為每個方案都是獨立的最值型用min或者max因為只需要保留最優(yōu)路徑。6.2 不同路徑從一維到二維的跨越LeetCode 62“不同路徑”是爬樓梯的二維版。一個機器人在m x n網格的左上角每次只能向下或向右走一步問到達右下角有多少條路徑。狀態(tài)定義從dp[i]變成dp[i][j]轉移方程從dp[i] dp[i-1] dp[i-2]變成dp[i][j] dp[i-1][j] dp[i][j-1]。沒有本質區(qū)別只是多了一個維度。但很多人第一次接觸二維DP時會覺得變了個物種其實不然。建議在刷完爬樓梯之后立刻刷這一題你會感覺一切都很順。6.3 爬樓梯的k階推廣滑動窗口優(yōu)化如果題目改成“每次可以爬1到k階”那么f(n) f(n-1) f(n-2) ... f(n-k)直接計算的話時間復雜度是O(nk)。如果k和n都很大比如n10^6k10^5就需要用前綴和或者滑動窗口來優(yōu)化。設sum[i] f(1) f(2) ... f(i)那么f(n) sum[n-1] - sum[n-k-1]。這樣每個f(n)都可以O(1)算出來整體降到O(n)。這是從爬樓梯這題延伸出去的一個不錯的進階點難度剛剛好不會讓人勸退但又確實需要動點腦筋。6.4 三步問題面試題庫里的孿生兄弟還有一個高頻變體叫“三步問題”也就是一次可以跨1、2、3階n可能到10^6要求對10^97取模。這個題比LeetCode原版更接近筆試實戰(zhàn)因為涉及了模運算。它的核心坑有兩個取模后相加可能要取兩次模f(n) (f(n-1) f(n-2) f(n-3)) % MOD取模不能改變中間態(tài)的精度所以每一步都要模踩過幾次之后你會形成一個條件反射看到“結果可能很大”立刻想到模運算看到n的范圍大過10^7立刻想到矩陣快速冪或者O(1)數學解。7. 我把這題的所有坑都踩了一遍給你整理一份避坑清單7.1 語言差異導致的溢出陷阱LeetCode原題n最大45結果在32位有符號整數范圍內2^31-1約21億而f(45)是1836311903剛好沒爆。但如果你用的是C的intf(46)就已經溢出變成負數了。所以很多C選手刷題時會把返回值類型寫成long long這個習慣是好的因為題目一旦擴展int根本扛不住。Java的int是32位long是64位但很多國內筆試場景為了防止溢出會要求輸出對10^97取模。如果你沒有養(yǎng)成取模的習慣那就得格外小心輸入范圍。python不存在這個問題Python的int是任意精度的這算是刷題時一個隱性優(yōu)勢但也容易讓人忽視溢出這個考點——面試問Java/C溢出問題時就會露餡。7.2 循環(huán)邊界range(3, n1)還是range(2, n)滾動數組寫法里循環(huán)邊界特別容易出錯。我用的是for i in range(3, n 1):當n3時循環(huán)會執(zhí)行一次算出f(3)。當n4時循環(huán)會執(zhí)行兩次先算f(3)再算f(4)。這個邊界寫對了答案就是對的。把n1寫成n的話n3就算不到f(3)直接返回錯誤的prev12。如果要精簡成a, b 1, 2 for _ in range(2, n): a, b b, a b return b if n 1 else a當n3時range(2, 3)只循環(huán)一次此時a2, b3返回b3正確。當n2時循環(huán)不執(zhí)行b2返回2正確。這種寫法可以少寫一個if分支但前提是你要理解range的終點是開區(qū)間。7.3 遞歸的返回值陷阱如果你寫備忘錄遞歸而且要處理n0的邊界那么if n 2: return n這個條件的n2包含了n0返回0。但如果你把條件寫成n1或n2分別return那就必須在函數入口先處理n0否則遞歸到n0時memo[0]可能沒初始化或者直接越界。7.4 面試中的“由淺入深”節(jié)奏最后說一個比較玄學但很重要的點面試時怎么講這道題決定了面試官對你的印象。我建議的答題節(jié)奏是四步走先確認題目邊界問清楚n的范圍和是否要求取模。說出最直觀的遞歸思路并主動指出它的指數級復雜度問題。緊接著給出DP解法并解釋狀態(tài)轉移是怎么從“最后一步”推導出來的。最后說“這個狀態(tài)轉移只依賴前兩項所以可以用兩個變量滾動優(yōu)化到O(1)空間”然后直接寫下最終代碼。這套流程下來面試官能看到你完整的思維鏈路而不是一個只會默寫答案的刷題機器。如果你還有余力可以補充一句“如果n極大可以用矩陣快速冪優(yōu)化到O(log n)”這就是錦上添花。我個人在刷這題時最大的體會是好題的評判標準不在于難而在于能不能用最簡單的外殼裝下整個算法體系的骨架。爬樓梯顯然就是這樣的題。你在這題上花兩個小時把每一層解法的來龍去脈都弄明白收益遠大于草草刷三四個不同題型的題。對了還有一個很容易被忽略的小細節(jié)LeetCode的題解區(qū)很多人喜歡寫“完全背包解法”把爬樓梯看成無限物品的完全背包。這個視角本身沒問題但是對于剛入門DP的新手我建議先不要把思路搞復雜。先把一維DP的基本模型吃透背包的視角等做到完全背包專題的時候再回頭來看你會發(fā)現原來這些題在更高維度上是相通的。