引言动态规划的核心在于将复杂问题分解为重叠子问题而「最小路径和」正是理解这一思想的经典范例。给定一个带权网格每次只能向下或向右移动求从左上到右下的最小路径和。这道题相比「粉刷房子」多了一个二维空间维度但状态转移更加直观——每个格子的值只依赖于其上方和左方的格子。本文将带你从 DP 表格构造到代码实现一步步掌握这道必刷题摘要本文详细解析力扣 LCR 099. 最小路径和的动态规划解法。给定m×n非负网格每次只能向下或向右走求左上到右下的最小路径和。定义dp[i][j]为到达(i,j)的最小路径和转移方程dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])上格子/左格子二者取较小值。重点讲解初始化边界第一行只能从左边来第一列只能从上边来需先填好第一行、第一列这种边界值然后再开始动态规划。提供二维数组和 O(n) 空间优化两种代码时间复杂度 O(m×n)目录一、题目描述二、动态规划思路1. 为什么用 DP2. DP 数组的定义3. DP 数组的构造以示例 1 为例第一步初始化 dp 数组第二步从 (1,1) 开始递推双层循环4. 状态转移方程三、Java 代码实现四、代码优化空间压缩五、易错点总结特别重要⚠️ 注意点 1初始化边界不能忘⚠️ 注意点 2理清上一步来自哪里⚠️ 注意点 3空间优化时一维数组的含义六、复杂度分析总结一、题目描述给定一个包含非负整数的m x n网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。示例 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二、动态规划思路1. 为什么用 DP到达(i,j)的最小路径和只依赖于到达上方(i-1,j)和左方(i,j-1)的最小路径和。因为每次只能向下或向右所以(i,j)的上一步只能是上面或左面——这就是最优子结构适合用 DP 自顶向下推导。2. DP 数组的定义dp[i][j]从左上角 (0,0) 走到 (i,j) 的最小路径和。3. DP 数组的构造以示例 1 为例输入grid [[1,3,1], [1,5,1], [4,2,1]]第一步初始化 dp 数组① 起点dp[0][0] grid[0][0] 1② 初始化第一行只能从左边来dp[0][j] dp[0][j-1] grid[0][j]即dp[0][1] dp[0][0] grid[0][1] 1 3 4dp[0][2] dp[0][1] grid[0][2] 4 1 5③ 初始化第一列只能从上边来dp[i][0] dp[i-1][0] grid[i][0]即dp[1][0] dp[0][0] grid[1][0] 1 1 2dp[2][0] dp[1][0] grid[2][0] 2 4 6初始化完成后dp 数组为下标\下标012014512待双层循环推导待双层循环推导26待双层循环推导待双层循环推导第二步从 (1,1) 开始递推双层循环对于非边界格子(i,j)其值 grid[i][j] min(dp[i-1][j], dp[i][j-1])dp[1][1] 5 min(dp[0][1]4, dp[1][0]2) 5 2 7dp[1][2] 1 min(dp[0][2]5, dp[1][1]7) 1 5 6dp[2][1] 2 min(dp[1][1]7, dp[2][0]6) 2 6 8dp[2][2] 1 min(dp[1][2]6, dp[2][1]8) 1 6 7完整 dp 数组下标\下标012014512762687最终答案dp[2][2] 74. 状态转移方程边界情况dp[0][0] grid[0][0]第一行dp[0][j] dp[0][j-1] grid[0][j]只能从左边来第一列dp[i][0] dp[i-1][0] grid[i][0]只能从上边来通用情况dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])三、Java 代码实现class Solution { public int minPathSum(int[][] grid) { //1.获取矩阵的行数和列数 int row grid.length; int col grid[0].length; //2.创建dp数组 int[][] dp new int[row][col]; //3.初始化dp数组初始化边界值第一行、第一列 //初始化左上角元素 dp[0][0] grid[0][0]; //初始化第一列 for (int i 1; i row; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } //初始化第一行 for (int j 1; j col; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } //4.开始动态规划的核心代码填充dp数组 for(int i1;irow;i){ for(int j1;jcol;j){ //到达当前节点的最小路径 当前格子的耗费路径 min(到达左面相邻格子的最小路径 到达上面相邻格子的最小路径) dp[i][j] grid[i][j] Math.min(dp[i][j-1], dp[i-1][j]); } } //返回结果 return dp[row-1][col-1]; } }运行结果四、代码优化空间压缩因为dp[i][j]只依赖于当前行的左方和上一行的同列所以可以用一维数组滚动更新空间复杂度降至O(n)public static int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[] dp new int[n]; // 初始化第一行 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] grid[i][j] Math.min(dp[j], dp[j-1]); // dp[j]旧值代表上方dp[j-1]新值代表左方 } } return dp[n-1]; }五、易错点总结特别重要⚠️ 注意点 1初始化边界不能忘很多同学直接写双层循环导致i0或j0时dp[i-1][j]或dp[i][j-1]越界。正确做法先单独初始化第一行和第一列再从(1,1)开始循环。⚠️ 注意点 2理清上一步来自哪里因为只能向下或向右走所以到达(i,j)的上一步只能是上方(i-1,j)或左方(i,j-1)不是四个方向也不是斜对角。⚠️ 注意点 3空间优化时一维数组的含义滚动数组版本中dp[j]在更新前代表上一行(i-1,j)的值dp[j-1]已经更新为当前行(i,j-1)的值所以Math.min(dp[j], dp[j-1])正好对应min(dp[i-1][j], dp[i][j-1])不要搞反顺序。六、复杂度分析版本时间复杂度空间复杂度二维数组O(m × n)O(m × n)一维滚动数组O(m × n)O(n)总结这道题是动态规划中路径类问题的入门经典核心思想是定义dp[i][j]为到达(i,j)的最小路径和先初始化边界由于第一行的每个格子只可能从左方格子而来第一列的每个格子只可能从上方的格子而来。所以此时初始化边界就是先初始化第一行、第一列的每个格子的值。通用转移dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])最终答案在dp[m-1][n-1]相比「粉刷房子」本题的 DP 表格多了一个空间维度但转移关系更加直观——上一步来自哪里一目了然。掌握这道题后可以继续挑战「不同路径」「三角形最小路径和」等同类问题。希望这篇文章能帮助你更好地理解动态规划如果有问题欢迎留言讨论