LeetCode 64最小路径和：Java动态规划与滚动数组优化精讲

这道题我印象太深了。“最小路径和”几乎是我当年准备Java后端面试时刷的第一道二维动态规划题，LeetCode 64题，难度中等，但它的套路几乎是所有路径类DP的“母题”。面试考它，不是要你背出答案，而是想看你有没有形成“状态定义、转移方程、边界初始化”的完整思维链。如果你最近在刷题、准备春招秋招，或者工作中突然要写一段带累计最优值逻辑的代码，这篇就聊透了。

1. 题目理解与动态规划的思维起点

1.1 题目描述与暴力解法为什么撑不住

先说题目本身。给定一个m x n的网格，每个格子里放着一个非负整数grid[i][j]，你从左上角(0,0)出发，每次只能向右走一步或者向下走一步，最终到达右下角(m-1,n-1)，要求找出一条路径，使得路径上所有格子的数字之和最小，返回这个最小值。

这个场景在真实业务里其实特别常见，比如地图导航、物流配送中计算最小成本路径；在算法面试里它就是“路径型动态规划”的模板题。很多人第一反应是暴力搜索，用DFS把所有从起点到终点的路径都枚举出来，再取最小和。思路没错，但复杂度撑不住。假设网格是20x20，从左上到右下总共要走38步，其中必须包含19次向右和19次向下，路径总数是组合数C(38, 19)，算出来差不多是3.5亿条。每条路径还要累加求和，整体运算规模根本不是面试场景里能接受的。数据再大一点，直接卡死。

暴力解法的问题在于它做了大量重复计算。不同的路径可能在中途汇聚到同一个格子，比如从(0,0)到(3,3)，可能有很多种走法，但一旦走到(3,3)之后，从(3,3)到终点的最优路径和是固定的，跟前面怎么走过来的没有关系。这个性质在动态规划里叫做“无后效性”，也就是未来只取决于当前状态本身，不取决于到达当前状态的历史过程。动态规划能高效求解，靠的就是抓住这一点。

1.2 为什么贪心在这里不成立

有些人会下意识想，每一步都选右边和下边里数字更小的那个不就行了？这叫贪心策略。但动态规划题里贪心经常出错，最小路径和就是一个典型反例。拿LeetCode的示例来测一下：

1 3 1 1 5 1 4 2 1

按贪心思路，起点在(0,0)，值是1，能走的下一步是右边3和下边1，选更小的下边1，到达(1,0)。接着能走的下一步是右边5和下边4，选更小的下边4，到达(2,0)。然后只能向右经过2到达终点1，整条路径和是1+1+4+2+1=9。但实际最优路径是1→3→1→1→1，路径和只有7。贪心在最开始贪了一个小数字1，结果被引到了一条数字更大的通道上，典型的“局部最优毁掉全局最优”。

那动态规划为什么能拿到正确答案？因为它不是每一步做“即时决策”，而是把整个问题拆成互相重叠的子问题，然后从最小的子问题开始逐个求解，用一张表把中间结果记录下来。这里最优子结构体现在：到格子(i,j)的最小路径和，一定等于格子本身的值加上“到达它上方格子的最小路径和”和“到达它左方格子的最小路径和”中较小的那一个。左、上两个子问题的答案一旦确定，当前格子的答案也就确定了，不可能有别的来源。

1.3 动态规划三步走：状态、转移、初始化

做任何DP题，都建议按三步来拆。

第一步，定义状态。我用dp[i][j]表示从左上角(0,0)出发，到达格子(i,j)时的最小路径和。注意这个状态含义必须包含“最小”这个语义，不能只是“路径和”，不然转移时你根本不知道该怎么组合。

第二步，写状态转移方程。到达(i,j)这个格子，只能从上方(i-1,j)下来，或者从左方(i,j-1)过来。既然要最小路径和，就取这两个来源中更小的那个，再加上当前格子的值。所以转移方程是：

dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])

第三步，确定边界和初始化。起点(0,0)没有左侧也没有上方，所以直接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[-1][j]或dp[i][-1]就直接数组越界了。

如果你觉得这套东西抽象，可以这么类比：想象你要建一栋楼，每间屋子的建造成本是grid[i][j]，而进入这间屋子的唯一办法是从左边那间走过来或从上边那间走下来。那么这间屋子累计的最低成本，就是左边屋子和上边屋子累计成本里更低的一个，加上当前屋子的基础成本。每间屋子的结果都只依赖已经算好的两间邻居，所以只要按从左到右、从上到下的顺序盖楼，整栋楼最低总成本一定算得出来。

2. Java实现：从二维DP到空间优化的完整演进

2.1 版本一：二维DP数组，最直观的写法

先把最标准的版本写出来。用一个和grid同维度的二维数组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 j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } 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]; }

代码里第一个if判空很多人会漏。如果传入的grid为null或者是一个空二维数组，后面的grid[0][0]会直接抛空指针异常。这道题LeetCode默认输入非空，但面试手写时要主动加这个防御，属于“健壮性”的加分项。

初始化第一行和第一列时要注意顺序。dp[0][0]必须先赋值，然后第一行从j=1开始累加，第一列从i=1开始累加。有的初学者喜欢把第一行和第一列放在双重循环里用条件判断处理，逻辑上可以，但代码会更啰嗦，而且每层循环都要做分支判断，效率也不如单独拉出来初始化来得干净。

这个版本的时间和空间复杂度都是O(mn)。时间上，每个格子只被访问常数次，不可能再快多少；空间上，存了整个dp表，长度为m * n。如果你现场把这段代码写完，面试官通常会追问一句“空间能不能省？”这就是进入优化的信号。

2.2 版本二：一维滚动数组，把空间降到O(n)

观察转移方程dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])，你会发现计算当前行时，真正用到的只有两样东西：上一行同一个位置的值dp[i-1][j]，和当前行左边位置的值dp[i][j-1]。更早之前的行用不到了，所以没必要把整张表都留着，只需要一个长度为n的一维数组，滚动复用就行。

这里有一个极其关键的细节，也是面试官最爱挖的坑：一维数组的遍历方向必须是从左到右正序，而不是倒序。原因是更新dp[j]之前，dp[j]里存的还是上一行第j列的值，也就是dp[i-1][j]；而dp[j-1]在正序遍历时已经被更新成当前行第j-1列的值，也就是dp[i][j-1]。这时候用Math.min(dp[j], dp[j-1])，恰好同时拿到了“上方”和“左方”两个来源。如果改成倒序遍历，dp[j-1]就还是上一行的旧值，结果直接错掉。

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[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] = dp[0] + grid[i][0]; for (int j = 1; j < n; j++) { dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]); } } return dp[n - 1]; }

在这个版本里，第一行初始化结束后，dp数组存的就是dp[0][j]。进入第一层循环处理第二行时，dp[0]要先累加grid[1][0]，因为第一列只能从上方来，没有左边的来源，所以它是在行循环开始时单独处理的。处理完dp[0]后，再正序遍历j=1到n-1，逐列更新。每次更新完成后，dp[j]就变成“当前行第 j 列”的值，为下一行的计算做好准备。

这个版本时间复杂度还是O(mn)，但额外空间从O(mn)降到了O(n)。如果网格是10000行、3列，空间差距就是上万倍，滚动数组的意义在长条形数据上体现得特别明显。

2.3 版本三：原地修改，把grid本身当作DP表

如果题目没有明确禁止修改原数组，其实连额外的一维数组都不用申请，直接在grid上累加就行。把grid[i][j]原地改成“到达该格子的最小路径和”，最终右下角的值就是答案。

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; for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; } for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; }

这个版本写起来非常短，额外空间是O(1)。但使用前一定要先想清楚两个问题。第一，如果面试官明确说“不能修改原数组”，这版就不能用，必须先问清楚数据约束；第二，即使题目没说不能修改，在实际工程里调用方可能还拿着原数组做其他运算，你直接把它改了会埋下隐蔽的bug。所以我个人的习惯是：面试先写二维版，再主动提出一维滚动数组优化，原地修改只在面试官追问“能不能O(1)空间”时拿出来，同时明确说明它的副作用。

2.4 三个版本如何选型

不同版本的应用场景不一样，我用一张表总结过自己的选型策略：

很多人一上来就追求一维滚动数组，觉得显得厉害。但面试更看重的是你能不能先把正确的思路讲清楚。二维版最容易和面试官对齐语义，也最难写错。先拿二维版把分拿稳，再一步步优化，这个节奏是最稳的。

3. 复杂度分析、路径还原与经典变体

3.1 为什么时间是O(mn)，还有没有更快的可能

从代码结构就能看出，不管哪个版本，外层循环遍历每一行，内层循环遍历每一列，每个格子都要参与一次状态转移，所以时间复杂度是O(mn)。能不能更快？理论上每个格子至少要访问一次才能确定它的最小路径和，所以O(mn)是这个问题的下界，常规思路下不可能突破。当然如果你考虑并行计算，把各行划分给不同线程，可以在多核环境下缩短墙钟时间，但算法复杂度本身的量级是不会变的。

面试时如果被问到“能不能更快”，可以像这样回答：不存在低于O(mn)的串行算法，因为每个格子的值都会影响最终结果；但如果网格规模特别大，可以用分治或并行思路做优化。这个回答既说明你理解复杂度下界，又展示了工程视野。

3.2 如果需要打印出最小路径，怎么实现

有很多题解只要求返回最小路径和，但实际面试里可能会延伸：“如果要把这条路径打印出来呢？”这时光存dp值就不够了，还要额外记录每一步的方向选择。我建议用二维版本加一个方向数组，因为一维滚动数组会把历史方向信息覆盖掉，很难还原。

思路是这样：当dp[i-1][j] < dp[i][j-1]时，说明从上方过来更优，记录pre[i][j] = 1；否则就是从左边过来更优，记录pre[i][j] = 0。全部计算完后，从右下角根据pre数组反向往回走，把经过的坐标收集起来，最后再反转顺序。

public List<int[]> minPathSumWithPath(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; int[][] pre = new int[m][n]; dp[0][0] = grid[0][0]; for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; pre[0][j] = 0; // 从左来 } for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; pre[i][0] = 1; // 从上来 } 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] = grid[i][j] + dp[i - 1][j]; pre[i][j] = 1; } else { dp[i][j] = grid[i][j] + dp[i][j - 1]; pre[i][j] = 0; } } } List<int[]> path = new ArrayList<>(); int i = m - 1; int 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; }

这个扩展非常值得在纸上手推一遍。你会发现当我们只知道“dp值最小”时，可能会有多个来源都取得同一个最小值，这时选择哪个来源都可以，因为路径和一样。但如果追求“字典序最小的路径”之类的附加条件，就需要额外定义比较规则了。

3.3 变体一：不同路径、三角形最小路径和、01背包

掌握了最小路径和，很多DP题都能触类旁通。

“不同路径”（LeetCode 62题）问的是从左上到右下有多少条不同的走法，转移方程变成dp[i][j] = dp[i-1][j] + dp[i][j-1]，不再是取最小值而是求和，边界上第一行和第一列全部初始化为1。这里你能看到同一个二维遍历框架，只是转移语义变了。

“三角形最小路径和”（LeetCode 120题）把网格换成了等腰三角形，每个位置只能向下一行的相邻位置移动，最经典的解法是从下往上DP，只用一维数组就能完成，状态转移是dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1])。它和最小路径和的差别在于三角形的每行长度不同，所以内层循环的边界要跟着当前行长度变化。

“01背包”则是完全不同的DP维度，但它的一维空间优化和最小路径和的滚动数组有非常微妙的关系。在01背包里，内层循环必须倒序，因为一维数组更新dp[cur]时，依赖的是上一轮计算出的更小容量的dp[pre]，如果正序遍历，dp[pre]已经被当前轮更新过，相当于同一件物品被放进了多次。而最小路径和之所以正序，是因为它依赖的“左方值”本来就应当来自当前轮的计算。把这两道题放在一起对比，你就能彻底弄懂“什么时候正序、什么时候倒序”这个几乎所有DP新手都会栽的坑。

3.4 大数溢出与防御性设计

还有一些细节值得在编码时考虑。如果grid[i][j]的数字很大，累加过程中可能超过Integer.MAX_VALUE，尤其是长路径下累计值会快速膨胀。LeetCode的常规用例一般不会触发溢出，但在真实项目中数据是不可控的。如果面试官追问“你会怎么处理”，可以回答：使用long类型做dp数组的中间计算，最后再转回int；或者在使用Math.min比较前先判断是否超过安全阈值。从实现层面，把二维DP的数组类型从int[][]换成long[][]，其他逻辑完全不用动。这个细节虽然简单，但能在面试中体现你对数值边界的敏感度。

4. 手写代码时常见的坑与调试技巧

4.1 四个高频翻车点

先说第一个坑：判空。grid可能为null，可能长度为0，也可能第一行长度为0，这三种情况都要在前面挡掉。写if (grid == null || grid.length == 0 || grid[0].length == 0)是最稳妥的。有时候第一行非空但后续行长度不一致，也就是“锯齿数组”，这种情况里n其实不恒定，需要先判断grid[i].length再进行循环，不然后面取grid[i][j]时会越界。

第二个坑：边界初始化顺序。很多人写完dp[0][0]就直接进双重循环，然后在循环里判断if (i == 0 && j == 0)或if (i == 0)，虽然结果可能对，但代码很乱，而且效率低。正确做法是把第一行和第一列单独处理，再从(1,1)开始双重循环。

第三个坑：一维滚动数组的遍历方向。前面反复强调了，正序还是倒序直接决定答案对错。如果你在写一维版时犹豫，有个自我检查方法：更新dp[j]时用的dp[j-1]必须已经是“当前行”的值，如果你希望它是“上一行”的值，那就得倒序。最小路径和需要当前行的dp[j-1]，所以正序。

第四个坑：返回值写错。二维版返回dp[m-1][n-1]，一维版返回dp[n-1]，原地修改版返回grid[m-1][n-1]。这个看起来简单，但人在紧张时真的会写串。写完代码后先口头说一遍“这个返回值对应哪个变量”，能大概率避免低级失误。

4.2 测试用例怎么设计才能覆盖全面

我建议至少准备这五类用例：

• 最小规模：[[5]]，返回5。这能验证边界初始化没有越界。
• 单行网格：[[1,2,3]]，返回6。验证第一行的累加逻辑。
• 单列网格：[[1],[2],[3]]，返回6。验证第一列的累加逻辑。
• 普通用例：[[1,3,1],[1,5,1],[4,2,1]]，返回7。验证转移方程是否真的取了最小值。
• 全0网格：[[0,0],[0,0]]，返回0。验证无正数路径时的表现。

如果是在线IDE里调试，可以用下面这段代码快速跑测试：

public static void main(String[] args) { Solution s = new Solution(); System.out.println(s.minPathSum(new int[][] {{5}})); System.out.println(s.minPathSum(new int[][] {{1, 2, 3}})); System.out.println(s.minPathSum(new int[][] {{1}, {2}, {3}})); System.out.println(s.minPathSum(new int[][] {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}})); System.out.println(s.minPathSum(new int[][] {{0, 0}, {0, 0}})); }

真实项目中，我会把单行、单列、全0这些边界情况写进单元测试，而不是只在脑子里过。尤其是单行单列，代码里第一行和第一列的初始化有一个小错就会直接暴露出来。

4.3 排错时最高效的调试方法

当结果和预期不符时，不要盯着代码干瞪眼。我的习惯是在双重循环里打印dp数组的每一行，肉眼对照手动推演的结果。比如用上面那个3x3的例子，手推二维DP表应该是：

1 4 5 2 7 6 6 8 7

右下角是7，正好是答案。如果你的程序打印出来的表在某个格子跟这个不一样，那么问题就锁定在那一行或那一列的初始化或转移逻辑上。手推和打印对照这个方法，比任何IDE断点都直观，尤其适合DP这类“错一处后面全错”的问题。

一维滚动数组出现错误时，还可以做个对照测试：写一个二维版本和一个一维版本，用同一组随机矩阵跑结果，只要有一次不一致，说明滚动数组的某个细节有问题，最常见的就是遍历顺序错了。

5. 面试复盘：从解题到表达的完整闭环

5.1 为什么面试官这么爱考这道题

这道题在LeetCode上是中等难度，在面试中出现的频率极高。因为它的难度卡在一个很微妙的位置：比斐波那契这种入门题复杂，又比编辑距离、最长递增子序列这种经典难题简单。它能考察候选人三个方面：能不能把实际问题抽象成状态；能不能写出正确的转移方程；能不能处理好边界条件和空间优化。这三个能力恰好是后端工程师设计缓存、处理动态规划类需求时最核心的底子。

5.2 拿到题目后的表达套路

在面试里，代码只是结果的一半，另一半是沟通。我建议按照“暴力思路 → DP定义 → 状态转移 → 边界处理 → 空间优化”的顺序来展开，而不是一上来就写代码。

开场可以说：“我先想到的是DFS暴力枚举所有路径，但路径数量是组合数级别，20x20的网格就有数亿条，肯定不行。然后我发现从任意格子到终点的最优路径和是固定不变的，和之前怎么走到这个格子无关，所以可以用DP。定义dp[i][j]为从左上角到(i,j)的最小路径和，它的来源只有上方和左方，所以转移方程是……”这样讲，面试官能清楚地看到你的思维轨迹，比直接丢出正确答案更有说服力。

写代码之前可以先用一个示例网格在脑子里跑一遍，标出dp值的变化，然后再落笔。面试官看到你不慌不忙、有章法，印象分会高不少。

5.3 从这道题延伸出去的复习路线

如果你正在准备Java面试，刷完最小路径和以后，建议按这个顺序巩固：不同路径 → 不同路径II（加了障碍物）→ 三角形最小路径和 → 最大正方形 → 编辑距离。这几道题能把二维DP和滚动数组的套路练得很扎实。

在Java语言层面，还要准备一些和这道题相关的常考点，例如递归到DP的转换过程、Java方法的传参引用机制、数组的默认初始化值。dp数组在Java里创建后默认全0，这会不会影响我们的正确性？最小路径和里每个格子都会被显式赋值，所以不受影响。但如果你把Math.max用在某些初始化值为0的场景，就要小心0是不是合法的初始值。这类语言细节，往往就是面试官在算法题之后追加的“小问题”。

关于热搜里频繁出现的“Java八股文”“Java面试大全”，我的建议是算法题和语言基础题都要兼顾，但算法题更重要的是解题思维而不是背题。你能把最小路径和从二维写到一维、从求值写到路径还原、从原题讲到变体，这一块的基本功就算过关了。面试不仅是考察你会不会这道题，更是考察你会不会这一类题。

最后分享一个自己的体会：当年我反复搞不懂一维滚动数组为什么正序时，教练只做了一件事，让我把二维dp表的三行并排写出来，然后把计算某一格时依赖的两个格子用箭头标出来。箭头从左和上同时指向当前格，我一下子就看明白了：一维数组里“左箭头对应的dp[j-1]”必须在本轮被更新过，而“上箭头对应的dp[j]”是上一轮的残留值。这个画面感比任何文字都管用。如果你刷这道题也有卡壳的地方，建议也把它画下来，画一遍，胜过背十遍。