最小路径和题目核心在一个 m \times n 的网格中寻找从左上角到右下角的路径使得路径上的数字总和最小。每次只能向下或向右移动。1. 核心状态转移方程无论使用哪种写法的代码核心逻辑永远是当前格子的最小值 min(上面走下来的值, 左边走过来的值) 当前格子的值数学表达式dp[i][j] \min(dp[i-1][j], \ dp[i][j-1]) grid[i][j]2. 解法一二维 DP (直观基础版) 思路创建一个和原网格一样大的dp表。dp[i][j]代表到达坐标 (i, j) 的最小路径和。填表顺序从左上往右下。边界初始化第一行只能从左边走过来累加。第一列只能从上面走下来累加。内部填充比较上和左的值取小的。 代码实现public int minPathSum(int[][] grid) { int rows grid.length; int cols grid[0].length; int[][] dp new int[rows][cols]; // 1. 起点初始化 dp[0][0] grid[0][0]; // 2. 初始化第一行 (只能向右走) for (int i 1; i cols; i){ dp[0][i] dp[0][i-1] grid[0][i]; } // 3. 初始化第一列 (只能向下走) for (int i 1; i rows; i){ dp[i][0] dp[i-1][0] grid[i][0]; } // 4. 填充中间 (比较左边和上边) for(int i 1; i rows; i){ for(int j 1; j cols; j){ // 比较上格 dp[i-1][j] 和左格 dp[i][j-1] dp[i][j] Math.min(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } return dp[rows-1][cols-1]; }•时间复杂度O(M \times N)•空间复杂度O(M \times N)3. 解法二一维 DP (空间优化版) 思路 (滚动数组)由于计算当前行时只依赖于“当前行左侧”和“上一行同列”的数据我们可以将二维数组压缩为一维数组dp[cols]。空间覆盖逻辑在更新dp[j]之前dp[j]存的是上一行的值等同于二维中的dp[i-1][j]。更新后的dp[j-1]存的是本行左侧的值等同于二维中的dp[i][j-1]。 代码实现public int minPathSum(int[][] grid) { int rows grid.length; int cols grid[0].length; int[] dp new int[cols]; // 1. 初始化第一行 dp[0] grid[0][0]; for (int i 1; i cols; i){ dp[i] dp[i-1] grid[0][i]; } // 2. 逐行推进 (从第二行开始) for(int i 1; i rows; i){ // 每行第一个元素只能从上方加下来 dp[0] grid[i][0]; for(int j 1; j cols; j){ // dp[j] (旧值) 是上方贡献dp[j-1] (新值) 是左方贡献 dp[j] Math.min(dp[j], dp[j-1]) grid[i][j]; } } return dp[cols-1]; }时间复杂度O(M \times N)空间复杂度O(N) 复习要点方向限制只能下/右决定了状态只来源于左和上。初始化第一行和第一列是“死路”只有一种走法必须先单独处理。优化直觉只要方程里只出现了i和i-1通常都可以优化到一维空间。