企业官网建设流程全解析

“最小路径和”这道题，LeetCode 上是第 64 题，也是动态规划入门阶段绕不开的一道经典题。题目本身一句话就能说完：一个 m 行 n 列的网格中每个格子有一个非负整数，从左上角走到右下角，每次只能向右或者向下走一步，求经过格子的数字之和的最小值。但就是这么一道题，考察过的点覆盖了递归、记忆化搜索、二维 DP、滚动数组、空间压缩，各家公司的面试里都值得拿出来细品。

我最近重新用 Java 把这道题完整过了一遍，干脆把整个思考链路、代码实现和踩坑记录整理出来。无论你是刚开始刷题的自学党，还是准备 Java 后端面试、想突击动态规划这一类题，这篇都能直接拿来作参考。

1. 题面拆解：先搞清楚问题再谈算法

1.1 题目到底在求什么

先看标准输入输出。方法签名一般是：

public int minPathSum(int[][] grid)

grid[i][j] 表示网格中第 i 行第 j 列的数字，i 从 0 到 m-1，j 从 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^(m+n))。我在本地测试过，m=n=15 的时候已经明显卡顿，m=n=20 基本等不出结果。

暴力递归的代价是“用递归树枚举每条路径”，而动态规划的改进恰恰是注意到：同一个子问题根本不需要算两遍。这就是动态规划能成立的根本前提，后面会详细展开。

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 来交替选择两行，i=1 时写在第 1 行，i=2 时又写回第 0 行，i=3 时再写第 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 数量级差不多的情况，直接用这个版本就够了。

三个版本对比一下：

这里多说一句：如果题目允许原地修改传入的 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 一套可复用的自测用例

算法题写完，自己先跑一遍用例再提交，是对自己负责。这里整理一套最小路径和的测试用例，覆盖常见边界：

自测的时候不要只看结果是不是对，还要顺手验证一下时间复杂度能不能撑住。LeetCode 原题给的范围是 m 和 n 最大 200，所以哪怕是二维 dp 也完全秒过。真正需要空间优化的动力，更多来自面试官的连环追问，以及你自己对“为什么会这样”的理解程度。

5. 从最小路径和延伸到面试与工程场景

5.1 变形一：要求输出具体路径怎么办

面试官常会追加一个问题：不光要最小值，还要把路径打印出来。这个时候只靠 dp 表不够，还需要额外记录每个格子是从哪个方向过来的。

思路是增加一个 pre 数组，pre[i][j] 为 1 表示从上方来，为 2 表示从左方来。每次取 min 的时候，把方向记下来。最后从终点回溯到起点，就能得到完整路径。

public List<int[]> 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; } } } // 从终点回溯 List<int[]> 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 表，把状态转移的过程落到纸上，而不是只把代码跑通。你会发现，那一张填满数字的表格，比任何模板都更能帮你理解动态规划的本质。