一、題目描述給定一個包含非負整數(shù)的m × n網(wǎng)格grid請找出一條從左上角到右下角的路徑使得路徑上的數(shù)字總和為最小。說明每次只能向下或者向右移動一步。示例 1輸入grid [[1,3,1],[1,5,1],[4,2,1]]輸出7解釋因為路徑 1→3→1→1→1 的總和最小。示例 2輸入grid [[1,2,3],[4,5,6]]輸出12約束m grid.lengthn grid[i].length1 m, n 2000 grid[i][j] 200二、問題分析這是一道經(jīng)典的網(wǎng)格型動態(tài)規(guī)劃Grid DP題目。它的核心特征最優(yōu)子結(jié)構(gòu)到達(i,j)的最優(yōu)路徑一定由到達其上方(i-1,j)或左方(i,j-1)的最優(yōu)路徑轉(zhuǎn)移而來。重疊子問題從不同路徑到達同一格子會重復(fù)求解相同子問題。無后效性一旦確定到達某格子的最小路徑和后續(xù)決策不受之前路徑形態(tài)影響。因為移動方向被限制為「只能向下或向右」所以不存在回路這為動態(tài)規(guī)劃的遞推順序提供了天然保證。三、狀態(tài)定義與轉(zhuǎn)移方程3.1 狀態(tài)定義設(shè)dp[i][j]表示從起點(0,0)走到格子(i,j)的最小路徑和。3.2 狀態(tài)轉(zhuǎn)移方程要到達(i,j)只可能從上方或左方來dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])3.3 邊界條件起點dp[0][0] grid[0][0]第一行i 0只能從左邊來dp[0][j] dp[0][j-1] grid[0][j]第一列j 0只能從上面來dp[i][0] dp[i-1][0] grid[i][0]3.4 最終答案dp[m-1][n-1]四、解法一標準二維動態(tài)規(guī)劃最直觀、最規(guī)范的寫法。新建一個與grid同尺寸的dp數(shù)組不修改輸入。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // dp[i][j] 從 (0,0) 走到 (i,j) 的最小路徑和 vectorvectorint dp(m, vectorint(n, 0)); // 初始化起點 dp[0][0] grid[0][0]; // 第一列只能從上面來 for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } // 第一行只能從左邊來 for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } // 其余格子取上面和左邊中較小的 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } };復(fù)雜度分析時間復(fù)雜度O(m × n)空間復(fù)雜度O(m × n)優(yōu)點邏輯清晰狀態(tài)定義和轉(zhuǎn)移方程一一對應(yīng)面試推薦首選。缺點額外占用O(m × n)空間。五、解法二一維滾動數(shù)組空間優(yōu)化觀察轉(zhuǎn)移方程dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]dp[i][j]只依賴上一行的同列dp[i-1][j]和本行的前一列dp[i][j-1]。因此可以把二維表壓縮成一維數(shù)組滾動更新。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // dp[j] 表示當前行第 j 列的最小路徑和 vectorint dp(n, 0); dp[0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { dp[j] dp[j - 1] grid[0][j]; } // 逐行更新 for (int i 1; i m; i) { dp[0] grid[i][0]; // 第一列只能從上面來 for (int j 1; j n; j) { dp[j] min(dp[j], dp[j - 1]) grid[i][j]; // dp[j] 更新前 上一行的值上面 // dp[j-1] 更新后 本行左邊的值左邊 } } return dp[n - 1]; } };關(guān)鍵點內(nèi)層循環(huán)中dp[j]在賦值前代表「上一行的dp[i-1][j]」賦值后代表「本行的dp[i][j]」。dp[j-1]已經(jīng)在本次內(nèi)層循環(huán)前一步更新代表「本行左邊的dp[i][j-1]」。順序必須從j 1向右保證左邊先更新。復(fù)雜度分析時間復(fù)雜度O(m × n)空間復(fù)雜度O(n)優(yōu)點不修改輸入空間降到O(n)。缺點一維語義略抽象需要理解「滾動更新」的時機。六、解法三原地修改 grid思路與二維 DP 完全一致只是把grid本身當作dp數(shù)組使用因為每個格子的原始值在計算完自身后不會再被用到。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 j 0) continue; else if (i 0) grid[i][j] grid[i][j - 1]; // 第一行 else if (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]; } };復(fù)雜度分析時間復(fù)雜度O(m × n)空間復(fù)雜度O(1)優(yōu)點空間最優(yōu)代碼短。缺點修改了輸入數(shù)組語義上犧牲了可讀性不適合要求保留原數(shù)據(jù)的場景。七、解法四DFS 記憶化自頂向下 DP7.1 為什么需要記憶化樸素 DFS 從(0,0)出發(fā)每次向下或向右遞歸會形成一棵龐大的遞歸樹。很多子問題如(1,1)會被重復(fù)訪問導(dǎo)致時間復(fù)雜度退化為指數(shù)級O(2^(mn))在大網(wǎng)格上必然超時。記憶化Memoization的核心思想用一個memo數(shù)組緩存每個狀態(tài)的結(jié)果遇到相同狀態(tài)直接返回。7.2 記憶化通用模板返回類型 dfs(狀態(tài)參數(shù)) { if (終止條件) return 終止值; // 1. 邊界 if (memo[狀態(tài)] ! 未計算標記) return memo[狀態(tài)]; // 2. 查表 結(jié)果 合并( dfs(子狀態(tài)1), dfs(子狀態(tài)2), ... ); // 3. 遞歸 memo[狀態(tài)] 結(jié)果; // 4. 寫表 return 結(jié)果; // 5. 返回 }7.3 本題實現(xiàn)class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // memo[i][j] 從 (i,j) 走到右下角的最小路徑和 // -1 表示未計算 vectorvectorint memo(m, vectorint(n, -1)); return dfs(grid, 0, 0, memo); } private: int dfs(vectorvectorint grid, int i, int j, vectorvectorint memo) { int m grid.size(), n grid[0].size(); const int INF 1e9; // 1. 邊界越界返回極大值保證 min 不會選它 if (i m || j n) return INF; // 2. 終止條件到達右下角 if (i m - 1 j n - 1) return grid[i][j]; // 3. 查表 if (memo[i][j] ! -1) return memo[i][j]; // 4. 遞歸只能向下或向右 int down dfs(grid, i 1, j, memo); int right dfs(grid, i, j 1, memo); // 5. 寫表并返回 memo[i][j] grid[i][j] min(down, right); return memo[i][j]; } };復(fù)雜度分析時間復(fù)雜度O(m × n)每個狀態(tài)只算一次空間復(fù)雜度O(m × n)memo 數(shù)組O(m n)遞歸棧7.4 記憶化常見坑坑說明未初始化標記memo默認全 0若答案是 0 會誤判為「未計算」應(yīng)用-1或INF標記狀態(tài)定義不完整若遞歸還依賴額外參數(shù)如剩余步數(shù)kmemo必須帶上該維度有環(huán)圖狀態(tài)間可互相到達時簡單記憶化會死循環(huán)需要額外visited或改迭代 DP按值傳表memo必須按引用傳遞否則每層遞歸拷貝效率驟降溢出用INT_MAX作不可達標記時參與加法會溢出建議用1e9