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