“最小路径和”这道题LeetCode 上是第 64 题也是动态规划入门阶段绕不开的一道经典题。题目本身一句话就能说完一个 m 行 n 列的网格中每个格子有一个非负整数从左上角走到右下角每次只能向右或者向下走一步求经过格子的数字之和的最小值。但就是这么一道题考察过的点覆盖了递归、记忆化搜索、二维 DP、滚动数组、空间压缩各家公司的面试里都值得拿出来细品。我最近重新用 Java 把这道题完整过了一遍干脆把整个思考链路、代码实现和踩坑记录整理出来。无论你是刚开始刷题的自学党还是准备 Java 后端面试、想突击动态规划这一类题这篇都能直接拿来作参考。1. 题面拆解先搞清楚问题再谈算法1.1 题目到底在求什么先看标准输入输出。方法签名一般是public int minPathSum(int[][] grid)grid[i][j] 表示网格中第 i 行第 j 列的数字i 从 0 到 m-1j 从 0 到 n-1。起点是左上角 (0,0)终点是右下角 (m-1,n-1)移动规则被限制得很死每次只能向右走一格或者向下走一格。这个“只能向右或向下”是整个问题的灵魂。它决定了两件事第一路径长度是固定的无论怎么走都需要走 (m-1) (n-1) 步第二到达任意格子 (i,j) 的上一步只会来自两个方向左边 (i,j-1) 或者上边 (i-1,j)。这两个特性一出来题目就已经从“搜索”变成了“递推”。很多初学者拿到题之后第一反应是走迷宫习惯性地想到 DFS、BFS、回溯。但注意看约束条件如果 m 和 n 都能到 200那么单纯枚举所有路径是指数级增长根本跑不完。所以这类题最自然的解法就是动态规划或者说动态规划就是为这种“每个状态只依赖前一状态”的问题量身定做的。1.2 小规模手算建立直觉先拿一个最经典的用例找找感觉grid { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }这个例子在 LeetCode 官方描述里出现过期望结果是最小路径和为 7。怎么来的路线是 1 → 3 → 1 → 1 → 1也就是先向右走两步再向下走两步。为什么这条线最优直观感受是所有路径里绕开了中间那个 5避免了额外开销。但你肉眼判断终究不严谨得有一个通法去证明。这个通法就是逐一比较所有可行路径把每个格子的“当前最小累计代价”都算出来。如果从 (0,0) 出发假设我们走一步到 (0,1)累计是 1 3 4走一步到 (1,0)累计是 1 1 2。再往后到 (1,1) 这个格子可以从 (0,1) 下来累计 4 5 9也可以从 (1,0) 过来累计 2 5 7。显然从 (1,0) 过来更划算。这时候就能看出门道计算每个格子时只要知道它左边和上边两个格子的最小累计代价取个较小值再加上当前格子就能得到当前格子的最小累计代价。整个过程可以像填表一样逐行推下去这就是动态规划的雏形。1.3 为什么暴力递归不行想通了上面的递推关系很多人会先写一个暴力递归把问题表达成函数调用public int minPathSum(int[][] grid) { return dfs(grid, grid.length - 1, grid[0].length - 1); } private int dfs(int[][] grid, int i, int j) { // 到达左上角返回当前格子的值 if (i 0 j 0) { return grid[0][0]; } // i 或 j 越界时返回无穷大表示这条路不通 if (i 0 || j 0) { return Integer.MAX_VALUE; } // 当前格子走法 当前格子的值 上方/左方路径和的最小值 return grid[i][j] Math.min(dfs(grid, i - 1, j), dfs(grid, i, j - 1)); }代码逻辑本身没有错但仔细一分析就会发现它包含了大量重复计算。dfs(1,1) 会被 dfs(1,2)、dfs(2,1) 各自调用而这些调用又会在不同分支里反复触发。网格规模一大重复调用的次数是指数增长的时间复杂度大约是 O(2^(mn))。我在本地测试过mn15 的时候已经明显卡顿mn20 基本等不出结果。暴力递归的代价是“用递归树枚举每条路径”而动态规划的改进恰恰是注意到同一个子问题根本不需要算两遍。这就是动态规划能成立的根本前提后面会详细展开。2. 动态规划是怎么一步步推出来的2.1 两个关键特征最优子结构 重叠子问题动态规划能解这道题不是因为它套了一个看起来很高级的名词而是因为问题本身具备两个特征。第一个特征叫最优子结构。从左上角走到 (i,j) 的最短路径一定会经过 (i-1,j) 或 (i,j-1) 中的一个。如果全局路径是最优的那么到达那个前驱格子的子路径也一定是最优的否则我换一条更短的子路径整体路径还能更短矛盾。这个性质保证了我们可以放心地用子问题的最优解去构造全局最优解。第二个特征叫重叠子问题。递归树里不同的路径会汇聚到同一个格子比如从上面下来和从左边过来都可能到达 (i,j)但一旦到达了这个格子后面面临的就是同一个子问题。暴力递归把这些重复的子问题一次次重新算算到天荒地老。动态规划换个姿态状态算一次就保存需要的时候直接查表。这里可以用一个生活化的类比你从家里出发去公司中间必须经过地铁换乘站。那么从家到公司的最短时间一定等于“从家到换乘站的最短时间”加上“从换乘站到公司的最短时间”。同时不管你今天走哪条路线你到达换乘站后面对的“剩余路程”都是同一个问题没必要每次到了换乘站再重新探路。动态规划就是提前把这个换乘站到公司的答案记下来直接查。2.2 状态定义与状态转移方程正式定义状态。设 dp[i][j] 表示从左上角 (0,0) 走到格子 (i,j) 的最小路径和。注意这个定义是带有“最小”二字的所以整个表里存的每个格子的值都是到达该格子的全局最优解。考虑怎么到达 (i,j)。题目规定只能向右、向下走所以上一步只有两种可能从上方来也就是从 (i-1,j) 向下走到 (i,j)路径和是 dp[i-1][j] grid[i][j]从左边来也就是从 (i,j-1) 向右走到 (i,j)路径和是 dp[i][j-1] grid[i][j]。因为题目要求最小值所以二选一取较小者dp[i][j] grid[i][j] Math.min(dp[i-1][j], dp[i][j-1])这就是状态转移方程也是整道题的核心。很多教程直接甩出这个式子但你可能还是会困惑为什么可以用 min因为 dp[i-1][j] 本身已经是到达上方格子的最小路径和了dp[i][j-1] 同理。到达当前格子的所有路径最后一步必然是从二者之一走过来的所以只要在两条“最后一步”路径里选累计代价最小的就行。这个 min 不是贪心而是对所有可行路径的完整枚举后取最优只不过动态规划把枚举结果压缩在状态表里了。2.3 边界初始化为什么不能省有了状态定义和转移方程还不能直接套双层循环因为 dp[0][0]、第一行、第一列这三个区域的格子没有完整的左边或上边。先看起点。dp[0][0] 没有任何前驱它的值就是 grid[0][0]这是整个递推的种子。再看第一行。第 0 行所有格子只能从左边一路向右走过来因为从上方根本没有格子。所以dp[0][j] dp[0][j-1] grid[0][j];再看第一列。第 0 列所有格子只能从上边一路向下走过来因为从左方没有格子。所以dp[i][0] dp[i-1][0] grid[i][0];边界初始化是新手最容易忽略的地方。很多人上来就写双重循环结果 Math.min 里面访问了不存在的 dp[-1][j] 或者 dp[i][-1]要么数组越界要么结果错得离谱。这个初始化不是可有可无的细节而是整个状态表的根基。3. Java 代码实现与空间优化三连3.1 二维 DP 完整版最直观、最好解释的写法按照上面的推导第一版代码可以这样写public int minPathSum(int[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } 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] grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; }这个版本的时间复杂度是 O(mn)空间复杂度也是 O(mn)。因为总共需要遍历每个格子一次每个格子的状态都记录在一个表里。好处是逻辑直观、容易调试打印 dp 表的时候每个格子的值一目了然。坏处是对于 m 和 n 都很大的情况它额外开辟了一个和原网格等大的二维数组。为什么说这个版本适合“先写对”因为写代码的第一要务永远是正确性。只有在保证逻辑无误的基础上讨论优化才有意义。面试的时候先把二维 DP 版本流利写出来已经能拿到基础分。接下来能主动做空间优化就会明显加分。3.2 滚动数组优化压缩空间的第一步观察状态转移方程可以发现一个关键事实计算 dp[i][j] 的时候只用到 dp[i-1][j] 和 dp[i][j-1]。换句话说某一行的计算只依赖上一行而不依赖上上行、上上上行。那些更早的行算完之后就再也没有用处了。那就可以只保留两行一行是“当前行”一行是“上一行”轮流使用public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; // 只需要两行空间 int[][] dp new int[2][n]; dp[0][0] grid[0][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) { // 当前行第一列只能从上方过来 dp[i % 2][0] dp[(i - 1) % 2][0] grid[i][0]; for (int j 1; j n; j) { // 上方 dp[(i-1)%2][j] 与 左边 dp[i%2][j-1] 取小 dp[i % 2][j] grid[i][j] Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]); } } return dp[(m - 1) % 2][n - 1]; }这里用 i % 2 来交替选择两行i1 时写在第 1 行i2 时又写回第 0 行i3 时再写第 1 行反复覆盖。空间复杂度从 O(m*n) 降到了 O(n)也就是只跟列数有关跟行数无关了。滚动数组本质上是在“时间换空间”不其实不是。它的时间复杂度和二维版本完全一样仍然是 O(m*n)只是把那些不再使用的旧状态的空间释放出来重复利用。理解这一点后你会发现它其实是很自然的压缩方式。3.3 一维数组终极版dp[j] 更新前后的含义滚动数组已经能应付大多数面试场景但还能再往前一步既然每次只会用到“上一行”和“当前行”而行号本身在写完当前行之后就不需要区分了那我们完全可以只用一个一维数组。思路是这样从左往右遍历到第 j 列时dp[j] 这个位置在更新之前存的是上一行第 j 列的结果也就是 dp[i-1][j]。而 dp[j-1] 已经在本轮更新过了它现在代表的是当前行第 j-1 列的结果也就是 dp[i][j-1]。于是转移方程变成了dp[j] grid[i][j] Math.min(dp[j], dp[j-1])更新前的 dp[j] 代表“上方的值”更新后的 dp[j-1] 代表“左边的值”。这一行代码同时利用了两个方向的信息非常巧妙。完整实现public 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] 此时仍是上一行第 0 列的值 dp[0] dp[0] grid[i][0]; for (int j 1; j n; j) { // dp[j] 更新前代表“上一行同列”dp[j-1] 已经是“当前行左边” dp[j] grid[i][j] Math.min(dp[j], dp[j - 1]); } } return dp[n - 1]; }一维版本的空间复杂度是 O(n)。如果列数远大于行数其实可以按行还是按列的方向动态调整但通常题目给的都是 m 和 n 数量级差不多的情况直接用这个版本就够了。三个版本对比一下实现版本空间复杂度代码复杂度适用场景二维 dp 数组O(m*n)低最直观教学演示、快速 AC、需要完整状态表滚动数组两行O(n)中等面试空间优化加分项一维数组O(n)中高需要理解更新顺序推荐实际书写兼顾简洁与高效这里多说一句如果题目允许原地修改传入的 grid 数组还能把空间压缩到 O(1)直接在 grid 上原地计算。但实际工程里直接修改入参是件很危险的事可能影响调用方的其他逻辑所以我一般不建议在生产代码里这么干。算法题图省事可以但要有意识地分清场合。4. 常见踩坑记录与实际排查技巧4.1 空数组与极端边界的处理第一个坑就是输入检查。LeetCode 这类题目一般会保证 grid 非空但如果你在实际项目里自己写工具方法或者被面试官要求补全健壮性就必须处理三种情况grid 为 null、grid.length 为 0、grid[0].length 为 0。更好的写法是在方法开头统一判断if (grid null || grid.length 0 || grid[0].length 0) { return 0; }不然直接用 grid[0].length 很可能直接抛 NullPointerException 或者 ArrayIndexOutOfBoundsException。这个习惯在写任何二维数组相关算法时都应该养成。还有一种容易被忽略的边界是 m 1 或 n 1。比如 grid 只有一行[[1,2,3]]此时第一行初始化循环已经把所有值都算出来了主循环完全不执行返回 dp[n-1] 就是 3。同理只有一列时也能正确返回。如果初始化和主循环的顺序写错了这一类边界用例就会挂。4.2 一维版本最容易写错的地方一维数组版本是我见过翻车最多的地方。很多人在写的时候会把内层循环想成“从左到右就行”但忽略了 dp[j] 的语义变化。关键点再强调一遍j 必须从左往右遍历。因为计算 dp[j] 时需要 dp[j-1] 已经是当前行的新值。一旦你写成从右往左遍历dp[j-1] 还是上一行的旧值整个状态转移就错了而且这种错误不是直接崩溃而是给出一个看似合理但实际错误的答案特别难排查。还有一个细节每一轮外层循环开始的时候dp[0] 需要单独更新。因为第一列只能从上方过来它依赖的是 dp[0] 在上一行时的旧值而不是任何“左边”的信息。很多人在一维版本里直接进入内层循环漏了 dp[0] 的更新结果第一列的所有值全部错位。我自己在本地调试的时候最常用的手段就是把每个版本的 dp 表打印出来逐行比对for (int i 0; i m; i) { System.out.println(Arrays.toString(dp[i])); }比如对 [[1,3,1],[1,5,1],[4,2,1]] 这个用例二维 dp 表最终应该是[1, 4, 5] [2, 7, 6] [6, 8, 7]终点 dp[2][2] 7和题目要求一致。如果你的表里某一行明显偏大或偏小就用一个 3×3 的手算对照基本一眼就能定位是初始化问题、更新顺序问题还是转移方程写错。4.3 一套可复用的自测用例算法题写完自己先跑一遍用例再提交是对自己负责。这里整理一套最小路径和的测试用例覆盖常见边界用例期望结果说明[[1]]11×1 网格无任何移动[[1,2,3]]6只有一行所有路径都是横着走[[1],[2],[3]]6只有一列所有路径都是竖着走[[1,2],[3,4]]72×2 网格最优是 1→2→4 或 1→3→4[[1,3,1],[1,5,1],[4,2,1]]7LeetCode 官方用例[[1,2,3],[4,5,6]]122×3 网格路径 1→2→3→6自测的时候不要只看结果是不是对还要顺手验证一下时间复杂度能不能撑住。LeetCode 原题给的范围是 m 和 n 最大 200所以哪怕是二维 dp 也完全秒过。真正需要空间优化的动力更多来自面试官的连环追问以及你自己对“为什么会这样”的理解程度。5. 从最小路径和延伸到面试与工程场景5.1 变形一要求输出具体路径怎么办面试官常会追加一个问题不光要最小值还要把路径打印出来。这个时候只靠 dp 表不够还需要额外记录每个格子是从哪个方向过来的。思路是增加一个 pre 数组pre[i][j] 为 1 表示从上方来为 2 表示从左方来。每次取 min 的时候把方向记下来。最后从终点回溯到起点就能得到完整路径。public Listint[] minPathWithTrace(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[m][n]; int[][] pre new int[m][n]; // 0:起点1:来自上方2:来自左方 dp[0][0] grid[0][0]; for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; pre[i][0] 1; } for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; pre[0][j] 2; } for (int i 1; i m; i) { for (int j 1; j n; j) { if (dp[i - 1][j] dp[i][j - 1]) { dp[i][j] dp[i - 1][j] grid[i][j]; pre[i][j] 1; } else { dp[i][j] dp[i][j - 1] grid[i][j]; pre[i][j] 2; } } } // 从终点回溯 Listint[] path new ArrayList(); int i m - 1, j n - 1; while (i 0 || j 0) { path.add(new int[]{i, j}); if (pre[i][j] 1) { i--; } else { j--; } } path.add(new int[]{0, 0}); Collections.reverse(path); return path; }注意回溯的时候 i 或 j 先减到 0 的情况此时 pre 数组里有对应的边界方向记录只要循环条件写成 i 0 || j 0 就能正确走到起点。这个变形题的价值在于它考察的不再是背模板而是你能否在状态流转过程中额外维护一条“前驱链”。5.2 变形二带障碍物或求最大路径和动态规划题的变形方向其实非常有套路。把最小路径和的转移方程里的 Math.min 换成 Math.max就变成了“最大路径和”问题。把某个格子设置成不可通行就变成了带障碍物的路径问题。带障碍物的处理逻辑很简单遇到障碍物时直接把 dp[i][j] 设置成一个极大值表示不可达或者直接跳过更新。但要注意边界初始化时也要判断障碍物否则第一行、第一列的错误状态会被一路带到终点。if (grid[i][j] -1) { dp[i][j] Integer.MAX_VALUE; // 障碍物不可达 } else { dp[i][j] grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]); }如果障碍物的格子很多导致终点不可达需要额外判断返回值是否等于极大值。这些都是做算法题容易忽略、但真实业务里必须考虑的场景。这类二维网格上的 DP 模型还能继续迁移到很多经典题比如不同路径、编辑距离、最大正方形。它们的共同套路都是定义 dp[i][j] 表示到 (i,j) 或处理到第 i、第 j 位时的某个最优值找出最后一步的所有可能取最优或求和然后初始化边界。动态规划在 Java 后端面试里是个大族“动态规划 dp 算法讲解”这类关键词之所以常年热门就是因为它是算法思维的一块硬骨头一旦吃透收益非常稳定。5.3 面试官真正想考察的是什么从面试角度拆解这道题也能看出一些门道。很多人以为面试官就是让你默写代码其实不然。一道最小路径和至少能考察出五个层次第一层能否快速定义状态。dp[i][j] 代表什么、为什么这么定义这是动态规划的核心基本功。状态定义错了后面全盘皆输。第二层能否推导转移方程。为什么是从上方或左方转移为什么取 min这里考察的是逻辑推导能力而不是记性。第三层能否处理边界初始化。第一行、第一列为什么需要单独处理这里考察的是严谨性和对状态定义的理解决心。第四层能否做空间优化。面试官追问“空间复杂度能不能降下来”时你如果立刻想到滚动数组说明你对状态依赖关系理解得足够深。第五层能否扩展变形。路径打印、障碍物、最大路径和、带权值变化这些都能看出你到底是真的理解了动态规划还是只是背了个模板。我见过很多候选人能把二维 dp 版代码一字不落写出来但被问到“为什么是 dp[i-1][j] grid[i][j] 而不是反过来”时就卡壳。反过来问我也见过一些朋友通过反复练这道题把整个动态规划题的思考框架建立起来了后面碰到新题也能举一反三。5.4 从算法题到工程能力的迁移可能有读者会问我平时写 Java 业务代码CRUD 居多这种算法题到底有什么用我的观点是大多数时候确实不会直接用到裸的最小路径和但动态规划背后的建模思想在真实系统里并不少见。比如资源分配问题若干个任务要分配给若干个执行单元每一步选择的累计收益或成本会影响最终结果这种递推关系本质上就是状态转移。再比如某些厂内的调度系统简化版的任务序列规划也会用到类似的 DP 思想。哪怕是做前端页面里的复杂表单联动校验状态机的思想也和 DP 一脉相承。更实际的理由是现在 Java 后端岗位面试算法题几乎是必考环节。动态规划又是算法题里出现频率最高的大类之一。与其临考前背一堆零散题解不如先把最小路径和这种基础题吃透理解了状态和转移同类题基本都能触类旁通。我个人在实际操作中的体会是动态规划的难点从来不是写代码而是“建模”。把现实问题抽象成状态、找出转移关系、定义清楚边界这三步一旦走通代码往往就是几行循环的事。最小路径和恰好是练习这套思维最合适的一道题因为它足够简单又没有简单到一眼看穿非常适合拿来作为动态规划的敲门砖。刷完这道题建议你一定自己手动画几遍 dp 表把状态转移的过程落到纸上而不是只把代码跑通。你会发现那一张填满数字的表格比任何模板都更能帮你理解动态规划的本质。