力扣 hot100 里的最小路徑和我前后刷過三遍。第一遍照著題解抄第二遍背狀態(tài)轉(zhuǎn)移方程第三遍才真正想明白一件事這道題難的不是“會(huì)寫動(dòng)態(tài)規(guī)劃”而是你能不能講清楚為什么要用 DP、一維空間優(yōu)化那行代碼為什么不是隨便寫的。如果你是剛接觸動(dòng)態(tài)規(guī)劃的讀者或者刷過但總覺得在背題這篇就按我自己的踩坑順序把它從暴力遞歸到一維優(yōu)化完整拆開講一遍。這道題本身非常標(biāo)準(zhǔn)給你一個(gè)m x n的網(wǎng)格每個(gè)格子有個(gè)非負(fù)整數(shù)從左上角出發(fā)每次只能向右或者向下走一步要你找一條到右下角的路徑讓路徑上所有數(shù)字之和最小。光看題面很多人第一反應(yīng)是“我每步都選值小的方向走不就行了”——這個(gè)想法錯(cuò)在哪后面我會(huì)單獨(dú)用一組數(shù)據(jù)驗(yàn)證。它被收進(jìn) hot100 列表不是因?yàn)橛卸嚯y而是因?yàn)樗鼛缀醢褎?dòng)態(tài)規(guī)劃最核心的思維全部濃縮進(jìn)去了狀態(tài)定義、邊界初始化、轉(zhuǎn)移方程、空間優(yōu)化一個(gè)不缺。這篇文章就沿著這條線一路拆保證你讀完能自己推導(dǎo)而不是背題。1. 為什么這道題值得單獨(dú)拆開寫一次先說結(jié)論最小路徑和是典型的動(dòng)態(tài)規(guī)劃入門題但它的價(jià)值遠(yuǎn)遠(yuǎn)不止“入門”兩個(gè)字。很多題解一上來就給你dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])然后說“初始化第一行第一列完事”。這套流程背起來容易可一旦題目換成帶障礙物的版本、要求輸出路徑、或者變成求最大路徑和你就懵了。根子在于沒有理解這個(gè)方程是怎么長(zhǎng)出來的。你看題面里有兩個(gè)關(guān)鍵約束只能向右走、只能向下走。這意味著什么意味著到達(dá)任意一個(gè)格子(i, j)的路徑最后一步只可能是從左邊(i, j-1)過來或者從上邊(i-1, j)過來。沒有第三種可能因?yàn)槟悻F(xiàn)在的位置決定了你不可能從右下角繞回來。這就是動(dòng)態(tài)規(guī)劃里常說的“最優(yōu)子結(jié)構(gòu)”如果從左上角到某個(gè)格子的路徑要最小那到達(dá)它前一步的那個(gè)格子也必須是“從左上角過來路徑最小”的狀態(tài)。你想啊假如到左邊格子的路徑和不是最小的那我完全可以用那條更小的路徑走到左邊再多走一步到當(dāng)前格子總代價(jià)不就更小了嗎這個(gè)邏輯本身就能自洽。還有一點(diǎn)容易被忽略這個(gè)問題具備“無后效性”。就是說一旦你走到了格子(i, j)之前是怎么走到這里的——走的是哪條具體路徑——都不影響你接下來怎么走。下一步能去的地方只取決于當(dāng)前坐標(biāo)跟歷史無關(guān)。這一點(diǎn)特別關(guān)鍵因?yàn)閯?dòng)態(tài)規(guī)劃本質(zhì)上就是在“剪掉歷史”只保留每個(gè)狀態(tài)的最優(yōu)值。如果你遇到一個(gè)問題發(fā)現(xiàn)“我怎么來的會(huì)影響我怎么走”那說明這個(gè)狀態(tài)定義不合適得換。另外暴力搜索里存在大量重復(fù)計(jì)算。簡(jiǎn)單說就是從不同的上方或左方格子走到同一個(gè)格子之后后續(xù)所有可能的路徑完全一樣但遞歸解法會(huì)把同一個(gè)格子反復(fù)求很多遍。這個(gè)特性叫“重疊子問題”正是 DP 能提速的根源。所以這道題同時(shí)包含了最優(yōu)子結(jié)構(gòu)、無后效性、重疊子問題三要素。把這三樣在腦子里面過一遍再去看狀態(tài)轉(zhuǎn)移方程它就是一個(gè)順理成章的結(jié)果不是一個(gè)需要硬記的公式。這就是我建議你認(rèn)真拆解這道題的理由。2. 先走一遍暴力遞歸狀態(tài)轉(zhuǎn)移方程就不是背的了很多人學(xué) DP 最大的誤區(qū)是直接看狀態(tài)轉(zhuǎn)移方程。我建議反過來先寫一個(gè)“最笨”的遞歸版本。不是說你要用它提交而是這一版能幫你把問題結(jié)構(gòu)看清楚。2.1 自頂向下思考從當(dāng)前位置出發(fā)的最小代價(jià)暴力遞歸的思路很直白定義dfs(i, j)表示從格子(i, j)走到右下角(m-1, n-1)的最小路徑和。那么答案就是dfs(0, 0)。怎么算這個(gè)函數(shù)很簡(jiǎn)單你在(i, j)你可以往右走到(i, j1)也可以往下走到(i1, j)。你并不知道哪條更好所以兩個(gè)方向都試一遍取代價(jià)小的那個(gè)最后再加上當(dāng)前格子的值。def min_path_sum(grid): m, n len(grid), len(grid[0]) def dfs(i, j): # 已經(jīng)到右下角路徑代價(jià)就是當(dāng)前格子的值 if i m - 1 and j n - 1: return grid[i][j] # 最后一行只能往右走 if i m - 1: return grid[i][j] dfs(i, j 1) # 最后一列只能往下走 if j n - 1: return grid[i][j] dfs(i 1, j) return grid[i][j] min(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)這個(gè)版本邏輯上完全正確。邊界條件也很直觀在最后一行時(shí)沒有下邊可走只能一路往右在最后一列時(shí)同理。只要不在邊界就朝兩個(gè)方向試探。你可以把dfs想象成一個(gè)不斷把問題遞歸分解的過程。每到一個(gè)格子你的決策空間只有兩個(gè)分支整個(gè)搜索樹就是一張從左上到右下的路徑圖。這個(gè)遞歸版本最大的好處是它和人類手工找路的思維方式一模一樣選擇太多的時(shí)候就試試完比大小。2.2 指數(shù)級(jí)成本與記憶化的自然過渡這個(gè)遞歸的時(shí)間復(fù)雜度是多少粗略看每個(gè)格子都會(huì)向兩個(gè)方向擴(kuò)展路徑數(shù)量是指數(shù)級(jí)的。精確點(diǎn)說不同的路徑條數(shù)是組合數(shù)C(mn, m)。就算網(wǎng)格只有 20×20路徑總數(shù)也已經(jīng)接近 3300 億條跑一次你就知道什么叫絕望。但更重要的問題是為什么會(huì)有這么多重復(fù)計(jì)算舉個(gè)例子你在(1, 2)這個(gè)格子上繼續(xù)往后走到終點(diǎn)的那段路徑和跟你從哪條路來到(1, 2)是無關(guān)的。可是在暴力遞歸里只要有一條不同的路徑到達(dá)(1, 2)它就會(huì)把dfs(1, 2)重新算一遍。到達(dá)同一個(gè)格子的路徑可能有很多條于是相同后綴路徑被反復(fù)求了成百上千次。解決辦法就是記憶化第一次算出dfs(i, j)之后把它存下來下次直接查表。from functools import lru_cache def min_path_sum_memo(grid): m, n len(grid), len(grid[0]) lru_cache(None) def dfs(i, j): if i m - 1 and j n - 1: return grid[i][j] if i m - 1: return grid[i][j] dfs(i, j 1) if j n - 1: return grid[i][j] dfs(i 1, j) return grid[i][j] min(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)這時(shí)候遞歸仍然是從上往下“遞”的思路但因?yàn)橛芯彺婷總€(gè)格子只會(huì)被真正計(jì)算一次時(shí)間復(fù)雜度從指數(shù)級(jí)降到了O(mn)。你會(huì)發(fā)現(xiàn)這不就是動(dòng)態(tài)規(guī)劃嗎本質(zhì)是一樣的。只不過 DP 把“遞歸緩存”的順序反過來從左上角開始自底向上填表。理解這一層你再看到狀態(tài)轉(zhuǎn)移方程就會(huì)覺得它是老朋友而不是從天而降的公式。3. 二維DP狀態(tài)定義、初始化順序和那個(gè)經(jīng)典例子的逐格演算記憶化遞歸和動(dòng)態(tài)規(guī)劃沒有本質(zhì)差別只是實(shí)現(xiàn)方向不同。二維 DP 版本就是用一個(gè)dp數(shù)組把每個(gè)狀態(tài)按依賴順序提前算好。3.1 狀態(tài)定義與邊界行、列的累加邏輯定義dp[i][j]為“從左上角(0, 0)到格子(i, j)的最小路徑和”。這和前面dfs的定義方向相反但結(jié)論等價(jià)。轉(zhuǎn)移方程是dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])為什么依賴的是dp[i-1][j]和dp[i][j-1]因?yàn)槟茏叩?i, j)的路徑最后一步只可能來自上方或左方。我們把這兩種可能里代價(jià)更小的那個(gè)狀態(tài)拿過來加上當(dāng)前格子的值就是到這個(gè)格子的最小代價(jià)。關(guān)鍵在初始化。dp[0][0]就是grid[0][0]這個(gè)沒疑問。問題是第一行和第一列。第一行的格子(0, j)因?yàn)樗厦鏇]有格子只能從左邊一路走過來所以dp[0][j] dp[0][j-1] grid[0][j]第一列的格子(i, 0)只能從上方一路走下來所以dp[i][0] dp[i-1][0] grid[i][0]這地方有個(gè)新手經(jīng)常寫錯(cuò)的點(diǎn)直接把整個(gè)dp數(shù)組初始化成grid然后只處理內(nèi)部格子。表面上看沒問題但如果你沒把第一行第一列累加內(nèi)部循環(huán)用到dp[i-1][j]或dp[i][j-1]時(shí)那還是原始網(wǎng)格值不是累計(jì)路徑和結(jié)果全錯(cuò)。所以邊界行、列必須單獨(dú)做累加。def min_path_sum(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] # 第一行 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] # 第一列 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] # 內(nèi)部格子 for i in range(1, m): for j in range(1, n): dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]如果你把grid換成[[1,3,1],[1,5,1],[4,2,1]]——這就是面試題里最常見的用例——最后答案是 7。接下來我逐格推一遍你就能看到數(shù)字是怎么流動(dòng)的。3.2 逐格推演為什么結(jié)果是 7而不是 6初始化后坐標(biāo)dp 值計(jì)算過程(0,0)1起點(diǎn)(0,1)41 3(0,2)54 1(1,0)21 1(2,0)62 4到這里第一行第一列已經(jīng)成了“前綴累計(jì)”的概念。接著看內(nèi)部(1,1)格子里是 5上方dp[0][1]4左方dp[1][0]2取小為 2加起來等于 7。(1,2)格子里是 1上方dp[0][2]5左方dp[1][1]7取小為 5加起來等于 6。(2,1)格子里是 2上方dp[1][1]7左方dp[2][0]6取小為 6加起來等于 8。(2,2)格子里是 1上方dp[1][2]6左方dp[2][1]8取小為 6加起來等于 7。所以答案是 7。對(duì)應(yīng)路徑是(0,0) → (0,1) → (0,2) → (1,2) → (2,2)也就是 1 3 1 1 1 7。這個(gè)例子很能說明問題如果你走1 → 1 → 5 → 1 → 1那條看起來更“中間”的路總和是 9反而更差。因?yàn)?DP 比較的是“累積代價(jià)”不是單步數(shù)值大小這跟人類預(yù)判路徑的直覺常常不一致。3.3 循環(huán)方向的選擇與復(fù)雜度分析二維 DP 的雙層循環(huán)外層按行從上往下內(nèi)層按列從左往右是最好理解也最常用的寫法。它背后的依賴關(guān)系是計(jì)算dp[i][j]時(shí)必須已知dp[i-1][j]和dp[i][j-1]。按行從上到下時(shí)上方那個(gè)值在上一輪已經(jīng)算好行內(nèi)從左到右時(shí)左邊那個(gè)值在當(dāng)前行已經(jīng)算好。所以這個(gè)順序是“拓?fù)溆行颉钡?。那換成外層按列、內(nèi)層按行可不可以也可以。只要保證每個(gè)狀態(tài)被計(jì)算時(shí)它依賴的上方、左方狀態(tài)都已經(jīng)存在即可。很多時(shí)候面試官會(huì)故意順著你的思路問“你外層為什么按行不是按列”你如果能說出“因?yàn)槲耶?dāng)前格子只依賴上方和左方按行遍歷能保證這兩個(gè)依賴都已就緒”這句話比悶頭寫代碼強(qiáng)很多。時(shí)間和空間復(fù)雜度都是O(mn)。這道題的網(wǎng)格規(guī)模通常不會(huì)太大二維數(shù)組開下來完全沒問題。但既然動(dòng)態(tài)規(guī)劃都學(xué)了下一步自然就要問這O(mn)的空間是不是可以再壓縮4. 空間優(yōu)化從二維壓到一維時(shí)覆蓋順序才是真正的坑空間優(yōu)化這一步是面試官最愛追問的地方也是網(wǎng)上題解寫得最粗糙的地方。很多人直接扔給你一行dp[j] grid[i][j] min(dp[j], dp[j-1])然后說“完事”。你要是沒理解覆蓋順序背下來也容易寫錯(cuò)。4.1 滾動(dòng)數(shù)組的本質(zhì)用“上一行的歷史值”比較“當(dāng)前行的新值”二維 DP 里計(jì)算第i行時(shí)其實(shí)只用到了兩樣?xùn)|西上一行i-1的整行數(shù)據(jù)以及當(dāng)前行已經(jīng)算出來的左邊格子。更早的行用不到了。所以我們可以用一個(gè)長(zhǎng)度n的一維數(shù)組dp讓它滾動(dòng)起來。這個(gè)數(shù)組在進(jìn)入第i行循環(huán)之前存的是第i-1行的結(jié)果。當(dāng)它從左往右更新時(shí)dp[j]在被賦值前代表“上方格子”的路徑和賦值后就變成“當(dāng)前位置”的路徑和而dp[j-1]已經(jīng)被更新成當(dāng)前行的值了正好代表“左邊格子”。這個(gè)“同一格先讀舊值、后寫新值”的順序就是滾動(dòng)數(shù)組的精髓。如果你把內(nèi)層循環(huán)改成從右往左那問題大了dp[j-1]還是上一行的舊值你會(huì)拿“上方”和“上一行的左方”去比較而不是“當(dāng)前行的左方”結(jié)果完全錯(cuò)誤。def min_path_sum(grid): m, n len(grid), len(grid[0]) # 先初始化第一行的滾動(dòng)數(shù)組 dp [0] * n dp[0] grid[0][0] for j in range(1, n): dp[j] dp[j-1] grid[0][j] # 從第二行開始滾動(dòng) for i in range(1, m): dp[0] grid[i][0] # 第一列只能從上往下累積 for j in range(1, n): dp[j] grid[i][j] min(dp[j], dp[j-1]) return dp[n-1]注意dp[0] grid[i][0]這行它處理的是第一列當(dāng)前dp[0]存的是上一行第一列的累計(jì)路徑和加上當(dāng)前行第一列的格子值正好是從起點(diǎn)一路走到這一列的新路徑和。4.2 一維更新過程的手工推演還用grid [[1,3,1],[1,5,1],[4,2,1]]這個(gè)例子。跑一遍你就知道覆蓋順序到底是怎么起作用的。第一行初始化后dp [1, 4, 5]。進(jìn)入第二行dp[0] grid[1][0]即1 1 2此時(shí)dp [2, 4, 5]。j1計(jì)算grid[1][1] min(dp[1], dp[0])也就是5 min(4, 2) 7更新dp[1]此時(shí)dp [2, 7, 5]。注意這里比較的是“上一行同列的上方值 4”和“當(dāng)前行已經(jīng)更新的左方值 2”剛好對(duì)應(yīng)二維 DP 里的min(dp[0][1], dp[1][0])。j2計(jì)算grid[1][2] min(dp[2], dp[1])也就是1 min(5, 7) 6更新后dp [2, 7, 6]。這正好是二維版本第二行的完整結(jié)果。進(jìn)入第三行同理dp[0] 4得到6。j12 min(7, 6) 8dp [6, 8, 6]。j21 min(6, 8) 7最終dp [6, 8, 7]。答案是dp[2] 7。和二維版本完全一致。如果你在紙上把這幾步寫一遍你會(huì)發(fā)現(xiàn)所謂“滾動(dòng)數(shù)組”就是讓同一行數(shù)組里的舊值和新值交替扮演角色。理解了這個(gè)你就不會(huì)再犯從右往左更新的錯(cuò)誤——除非你要實(shí)現(xiàn)的是一維背包那種特殊場(chǎng)景那時(shí)才需要刻意反向遍歷。4.3 寫成二維還是直接寫一維面試?yán)锏某尸F(xiàn)策略我的建議是除非題目明確限制空間否則先把二維版本寫出來再順嘴提一句“這里可以用滾動(dòng)數(shù)組壓到 O(n)”。這不是廢話而是給面試官展示你的推導(dǎo)能力。直接甩一維版本雖然代碼簡(jiǎn)潔但有時(shí)候別人會(huì)懷疑你是不是背的你先二維再一維邏輯鏈條完整反而更容易得到認(rèn)可。另外一個(gè)細(xì)節(jié)按列壓縮也是可以的dp長(zhǎng)度取m外層遍歷列內(nèi)層遍歷行。但按行壓縮寫的人更多而且面試官一般也就默認(rèn)這個(gè)寫法。你只要保證自己知道為什么從左往右而不是從右往左就行別在這上面翻車。5. 原地修改、邊界case以及“每步貪心”這個(gè)直覺陷阱這道題還有兩個(gè)經(jīng)常被忽略的點(diǎn)能不能直接改原數(shù)組、以及“貪心選擇”為什么行不通。這兩個(gè)點(diǎn)恰恰是面試追問的高頻區(qū)。5.1 原地修改的適用邊界與 integer 溢出分析如果你不想額外開數(shù)組可以直接在原grid上累加。因?yàn)間rid[i][j]更新之后后續(xù)只會(huì)有右方和下方的格子用到它不會(huì)再回頭讀取原始值所以覆蓋是安全的。def min_path_sum(grid): m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): if i 0 and j 0: continue if i 0: grid[i][j] grid[i][j-1] elif j 0: grid[i][j] grid[i-1][j] else: grid[i][j] min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]但這里有個(gè)隱患原地修改改變了函數(shù)的入?yún)?。在?jìng)賽平臺(tái)里這沒問題可如果是工程代碼調(diào)用方可能還指望grid保持原樣用于別處。所以我會(huì)先問一句“可以修改輸入數(shù)組嗎”確認(rèn)之后再?zèng)Q定用不用原地方案。還有個(gè)衍生問題路徑和會(huì)不會(huì)溢出力扣這道題的約束是網(wǎng)格m, n不超過 200每個(gè)格子值是非負(fù)整數(shù)。就算極端情況所有格子都是 200一條路徑上的最大和也就200 * 200 * 200 8000000遠(yuǎn)在int安全范圍內(nèi)。但你要是把網(wǎng)格放大一百倍或者在面試題里被擴(kuò)展成大數(shù)值場(chǎng)景那int就不一定穩(wěn)了。用 Python 或 Go 的人不太擔(dān)心這一點(diǎn)但用 C/Java 寫的時(shí)候提一句“這里需要確認(rèn)數(shù)據(jù)范圍夠不夠”是加分行為。5.2 反直覺例子局部最優(yōu)不等于全局最優(yōu)回到開頭說的那個(gè)陷阱很多人覺得每步選右邊和下邊里值更小的方向走就行這就是貪心。我舉一個(gè)例子讓你死心grid [ [1, 2, 1], [1, 100, 1], [3, 1, 1] ]從(0,0)出發(fā)右邊是 2下邊是 1貪心策略會(huì)走下邊。走到(1,0)后右邊是 100下邊是 3貪心繼續(xù)走下邊。然后一路右移到終點(diǎn)路徑是1 1 3 1 1 7。但真正的答案是多少走(0,0) → (0,1) → (0,2) → (1,2) → (2,2)總和是1 2 1 1 1 6。貪心因?yàn)榈谝徊截澚四莻€(gè)“看起來小的 1”結(jié)果把自己逼進(jìn)了一條后續(xù)代價(jià)很高的區(qū)域反而先橫向走兩步、避開 100 和大片 3整體更劃算。這個(gè)例子說明路徑類問題的局部最優(yōu)沒法拼出全局最優(yōu)因?yàn)槟隳芸吹降闹皇钱?dāng)前一步而前面一小步的差異會(huì)決定后面遇到哪些格子。這也是為什么這類題不能用貪心、必須用動(dòng)態(tài)規(guī)劃的原因——DP 的就是“全局最小”而不是“每步最小”。5.3 如果要求輸出完整路徑DP要怎么改造很多面試官會(huì)在你寫完最小路徑和后追加一個(gè)問題“返回最小路徑的坐標(biāo)不止返回和。”這時(shí)候一維滾動(dòng)數(shù)組就不夠用了因?yàn)槟阋厮菝恳徊奖仨氈烂總€(gè)格子到底是從上方來的還是從左方來的。最簡(jiǎn)單的改造是在二維 DP 之外再開一個(gè)pre[i][j]記錄來源方向。比如0表示來自上方1表示來自左方。填完 DP 表后從終點(diǎn)開始按照pre反向走回起點(diǎn)再把路徑翻轉(zhuǎn)過來。def min_path_sum_with_path(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] pre [[0] * n for _ in range(m)] # -1 起點(diǎn), 0 上, 1 左 dp[0][0] grid[0][0] pre[0][0] -1 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] pre[0][j] 1 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] pre[i][0] 0 for i in range(1, m): for j in range(1, n): if dp[i-1][j] dp[i][j-1]: dp[i][j] grid[i][j] dp[i-1][j] pre[i][j] 0 else: dp[i][j] grid[i][j] dp[i][j-1] pre[i][j] 1 path [] i, j m - 1, n - 1 while True: path.append((i, j)) if pre[i][j] -1: break if pre[i][j] 0: i - 1 else: j - 1 path.reverse() return dp[m-1][n-1], path這個(gè)需求一加上空間優(yōu)化就省不下來了——回溯需要全量信息一維數(shù)組存不了“每個(gè)格子的來源”。這也算是一個(gè)很好的面試互動(dòng)先壓空間展示能力再遇到輸出路徑的要求時(shí)自然過渡回二維說明你知道權(quán)衡。6. 從最小路徑和出發(fā)同一DP模型在變式題里的三種變化刷題最重要的是舉一反三。最小路徑和不是孤立的一道題它和不同路徑、不同路徑 II 共享同一個(gè)骨架只是狀態(tài)轉(zhuǎn)移方程的內(nèi)容不同。下面我把這些變化整理一下方便你橫向?qū)Ρ取?.1 從求最小到求方案數(shù)62/63題的遷移規(guī)律力扣的不同路徑題問的是從(0,0)到(m-1,n-1)有多少條不同走法。同樣是只能向右向下狀態(tài)定義幾乎一樣dp[i][j]表示從起點(diǎn)到(i,j)的方案數(shù)。轉(zhuǎn)移方程變成了dp[i][j] dp[i-1][j] dp[i][j-1]注意區(qū)別求路徑和的時(shí)候dp[i][j]是“當(dāng)前格子值 兩種來源路徑和的最小值”求方案數(shù)時(shí)沒有格子值并且要的是“兩種來源的方案數(shù)之和”。初始化也不同第一行、第一列不再是累加格子值而是全部設(shè)成 1因?yàn)橹挥幸粭l直線走法。到了不同路徑 II帶障礙物處理方式稍微復(fù)雜一點(diǎn)。如果grid[i][j] 1說明這里不能走直接dp[i][j] 0。真正的坑在第一行第一列的初始化如果第一行里有一個(gè)障礙那么障礙位置以及它右邊的所有格子都到不了都應(yīng)該設(shè)成 0不能繼續(xù)賦值 1。同樣的道理適用于第一列。這個(gè)細(xì)節(jié)和最小路徑和的“前綴累加”有異曲同工之處都是相同方向的連鎖效應(yīng)。下面是三種題型的對(duì)比題目類型狀態(tài)含義轉(zhuǎn)移方程初始化特點(diǎn)最小路徑和到(i,j)的最小累計(jì)代價(jià)grid[i][j] min(上方, 左方)第一行、第一列累加不同路徑到(i,j)的走法數(shù)上方 左方第一行、第一列為 1帶障礙不同路徑到(i,j)的走法數(shù)障礙處為 0同上障礙格子跳過遇到障礙后邊界行/列置 06.2 多起點(diǎn)、多終點(diǎn)、帶障礙物時(shí)的初始化差異還有一種常見變形是“超級(jí)源點(diǎn)/超級(jí)匯點(diǎn)”問題起點(diǎn)不是(0,0)終點(diǎn)也不是右下角而是給定的幾個(gè)點(diǎn)位。這時(shí)候一般做法是在 DP 前掃一遍所有可能起點(diǎn)或者人為加一層“虛擬行列”讓初始化變統(tǒng)一。比如題目改成“可以從左上角區(qū)域任一邊界點(diǎn)出發(fā)到達(dá)右下區(qū)域任一目標(biāo)點(diǎn)”那你可以把邊界上所有可能的起點(diǎn)都預(yù)先初始化為各自格子的值然后再進(jìn)入常規(guī) DP。本質(zhì)上還是同一個(gè)模型但如果你只會(huì)死記“第一行第一列累加”這種變化就會(huì)卡住。添加障礙物時(shí)也類似如果grid[i][j]是障礙dp[i][j]要直接設(shè)成一個(gè)“無效值”。求最小值時(shí)用正無窮求方案數(shù)時(shí)用 0。這個(gè)通用技巧幾乎適用所有網(wǎng)格 DP。6.3 個(gè)人刷題心得為什么建議用它作為DP入坑的第一道題我自己刷這道題的幾次返工經(jīng)歷最有價(jià)值的領(lǐng)悟是先寫暴力遞歸再寫記憶化最后才寫 DP 和空間優(yōu)化。這個(gè)順序比直接背狀態(tài)轉(zhuǎn)移方程慢但它把“為什么 DP 是對(duì)的”變得特別具體。后來我再遇到新的動(dòng)態(tài)規(guī)劃題腦子里會(huì)先浮現(xiàn)遞歸函數(shù)長(zhǎng)什么樣而不是干巴巴的方程。建議第一次接觸 DP 的人這樣練找?guī)椎馈懊總€(gè)格子只依賴上方和左方”的題目最小路徑和是其中最標(biāo)準(zhǔn)的代表。把它吃透接著做不同路徑、帶障礙版本然后把min換成max做最大路徑和再想想如果允許走上下左右四方向?yàn)槭裁雌胀?DP 就不靈了——因?yàn)槟菚r(shí)會(huì)出現(xiàn)環(huán)需要換成最短路算法。這一套組合拳打下來你對(duì)“狀態(tài)、轉(zhuǎn)移、邊界”這幾個(gè)詞的理解會(huì)完全不一樣。最后再分享一個(gè)小技巧不要只在腦子里推演拿一張紙、一個(gè)很小的網(wǎng)格手工畫一遍滾動(dòng)數(shù)組的更新過程。你花十分鐘畫完這張表之后遇到任何類似的空間優(yōu)化題都會(huì)比別人穩(wěn)很多。