LeetCode 64最小路径和1. 题目核心给定一个m × n的非负整数网格grid从左上角(0,0)出发到右下角(m-1,n-1)每次只能向右 向下要求找到一条路径使经过的所有数字之和最小并返回这个最小路径和。例如1 3 1 1 5 1 4 2 1最优路径1 → 3 → 1 ↓ 1 ↓ 1路径和1 3 1 1 1 72. 思路一DFS / 枚举所有路径从(0,0)开始每个位置尝试向右 向下一直走到右下角计算每条路径的数字总和最后取最小值。这种方法逻辑直观但会产生大量重复搜索例如同一个位置(i,j)可以通过很多不同路线到达而到达之后的后续路线会被重复计算因此效率较低。3. 思路二动态规划 DP3.1 DP 状态定义定义dp[i][j]表示从左上角(0,0)走到(i,j)时可以得到的最小路径和。注意这题和上一题“不同路径 II”很像但含义完全不同不同路径 dp[i][j] 到达当前位置有多少条路径 最小路径和 dp[i][j] 到达当前位置的最小数字总和3.2 为什么只看上面和左边机器人只能向右 向下所以想走到(i,j)最后一步只能来自上面(i-1,j) 左边(i,j-1)假设从上面到达时最小路径和 10 从左边到达时最小路径和 7 当前格子的值 3显然应该选择左边7 3 10而不是10 3 13所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];3.3 为什么这里用min上一题却用上一题“不同路径”求的是一共有多少种方案因此dp[i][j] dp[i - 1][j] dp[i][j - 1];这题求的是所有方案中哪一个代价最小所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];可以记求方案总数 → 求最大值 → max 求最小值 → min4. 初始化4.1 起点到达起点(0,0)什么地方都不用走因此路径和就是当前格子的值dp[0][0] grid[0][0];4.2 第一列第一列的格子只能从上面走下来(0,0) ↓ (1,0) ↓ (2,0)所以dp[i][0] dp[i - 1][0] grid[i][0];例如grid 1 1 4那么dp 1 2 64.3 第一行第一行只能一直向右(0,0) → (0,1) → (0,2)所以dp[0][j] dp[0][j - 1] grid[0][j];5. 示例完整推导对于grid 1 3 1 1 5 1 4 2 1初始化起点dp 1 ? ? ? ? ? ? ? ?初始化第一行dp[0][0] 1 dp[0][1] 1 3 4 dp[0][2] 4 1 5得到1 4 5 ? ? ? ? ? ?初始化第一列dp[1][0] 1 1 2 dp[2][0] 2 4 6得到1 4 5 2 ? ? 6 ? ?计算(1,1)min(上面4, 左边2) 5 2 5 7计算(1,2)min(上面5, 左边7) 1 5 1 6计算(2,1)min(上面7, 左边6) 2 6 2 8计算(2,2)min(上面6, 左边8) 1 6 1 7最终 DP1 4 5 2 7 6 6 8 7因此答案 dp[2][2] 76. C二维 DP你截图中的思路和代码就是这个标准解法。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); 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]; } };7. Java二维 DPJava 使用的是完全相同的动态规划思路。class Solution { public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[m][n]; 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] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } }8. Java 语法解释8.1 二维数组int[][] grid对应 Cvectorvectorint grid8.2 获取行数和列数Javaint m grid.length; int n grid[0].length;Cint m grid.size(); int n grid[0].size();Java 数组使用.length没有括号。8.3 创建二维数组int[][] dp new int[m][n];表示创建一个m × n的二维整数数组默认所有元素初始化为0。8.4Math.minJavaMath.min(a, b)对应 Cmin(a, b)所以dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];就是选择从上面和左边过来时路径和更小的那一个再加当前格子的值。9. Python二维 DPPython 同样使用相同的 DP。class Solution: def minPathSum(self, grid): m len(grid) n len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] # 初始化第一列 for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] # 初始化第一行 for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] # 状态转移 for i in range(1, m): for j in range(1, n): dp[i][j] ( min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] ) return dp[m - 1][n - 1]10. Python 语法解释10.1 获取二维数组大小m len(grid)n len(grid[0])len(grid)是行数len(grid[0])是列数。10.2 创建二维数组dp [[0] * n for _ in range(m)]例如m 3 n 3得到[ [0,0,0], [0,0,0], [0,0,0] ]10.3 Python 的minmin(a, b)直接得到两个数中更小的一个。10.4range(1, m)for i in range(1, m):表示i 1,2,...,m-1对应 Cfor (int i 1; i m; i)11. 空间优化一维 DP因为dp[i][j]只依赖上面 dp[i-1][j] 左边 dp[i][j-1]所以可以只保存一行。使用dp[j]表示当前处理到第j列时的最小路径和。更新前dp[j] 上面那个格子的最小路径和而dp[j-1] 当前行左边格子的最小路径和所以dp[j] min(dp[j], dp[j - 1]) grid[i][j];空间复杂度可以从O(m × n)降低到O(n)12. C一维空间优化class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); 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]; } } return dp[n - 1]; } };13. 复杂度二维 DP时间复杂度O(m × n) 空间复杂度O(m × n)一维 DP时间复杂度O(m × n) 空间复杂度O(n)14. 与 LeetCode 63 的联系两道题几乎是同一个网格 DP 模板。LeetCode 63不同路径 II求有多少条路线所以dp[i][j] dp[i - 1][j] dp[i][j - 1];LeetCode 64最小路径和求哪条路线数字之和最小所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];它们共同的地方都是当前位置只能从 上面 左边 过来区别只是题目问的东西不同统计所有方案 → 相加 选最优方案 → min/max15. 核心记忆DP 定义dp[i][j] 从左上角走到 (i,j) 所能得到的最小路径和初始化dp[0][0] grid[0][0]; dp[i][0] dp[i - 1][0] grid[i][0]; dp[0][j] dp[0][j - 1] grid[0][j];状态转移dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];最后只记一句到当前格子的最小路径和 上面和左边两个来源中更小的路径和 当前格子的数字。