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