企业官网建设流程全解析

刷算法题有一段时间的人，大概率会碰到这么一道经典题：给你一个二维矩阵，从左上角走到右下角，每次只能向右或者向下走一格，求路径上所有数字之和的最小值。牛客上这道题编号是BM68，题名就叫“矩阵的最小路径和”。我最初做这道题的时候，第一反应是按惯例从左上角开始推，但后来仔细把“从下至上”的倒推方式捋了一遍，发现这个反向思路不仅代码写起来更顺手，在理解动态规划的状态依赖关系时也清晰很多。

这篇文章就把我完整的思考过程、状态转移推导、三种空间复杂度的写法、以及和01背包的对照心得一次说透。无论你是刚接触动态规划的新手，还是想快速刷题找感觉的求职党，照着这篇文章的思路走一遍，这题基本就吃透了。

1. 题目理解与从下至上的核心思路

1.1 题目到底在问什么

先说题目本身。给定一个 m 行 n 列的矩阵 grid，每个格子里有一个非负整数，你从左上角 grid[0][0] 出发，每一步只能向右或者向下移动，最终到达右下角 grid[m-1][n-1]，要求把所有经过格子上的数字加起来，找到所有可行路径中和最小的一条，返回这个最小和。

举个例子，如果矩阵是：

1 3 1 1 5 1 4 2 1

那最小路径走法是 1 → 3 → 1 → 1 → 1，路径和是 7。你也可能走出 1 → 1 → 4 → 2 → 1 得到 9，但显然不是最优。这里的关键约束就是“只能向右和向下”，这个约束直接决定了这道题能用动态规划做，而且做起来很轻松。为什么？因为这意味着每个格子只能从它上方或者左方走来，不会出现回头路，天然就是一个有向无环图结构，DP的“无后效性”天然满足。

1.2 为什么倒着推反而更顺

我见过很多题解都是从左上角正向推：dp[i][j] 表示从起点到 (i,j) 的最小路径和，然后 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。这个思路没错，但“从下至上”的倒推视角其实更贴合递归直觉：我不去想“我从哪里来”，而是想“我要往哪里去”。

从右下角出发，站在任意一个格子 (i,j) 上，如果我要走到右下角，那我只能选择去右边的格子 (i,j+1)，或者下边的格子 (i+1,j)。选哪边？当然是选对应子问题结果更小的那一边。这个思考方式非常自然，因为“朝终点走”比“从起点追忆”更符合方向感。

我的经验是，很多新手一上来就用正向思路写，结果在边界处理上很容易犯迷糊：第一行只能从左往右来，第一列只能从上往下来，稍不注意下标就写错了。而从下至上的写法里，最后一行只能向右走、最后一列只能向下走，位置和方向是固定的，写起来更直观，返工概率低得多。

1.3 状态定义与初值思考

在这个倒推视角下，状态定义就是：

dp[i][j] 表示从格子 (i,j) 出发，走到右下角 (m-1,n-1) 的最小路径和。

最终答案自然就是 dp[0][0]。初始化的时候，我们让 dp[m-1][n-1] = grid[m-1][n-1]，因为终点格子自己走到自己，不需要额外多走任何一步，路径和就是它本身的值。

关键是转移方向。因为 dp[i][j] 依赖的是它下边和右边的格子，也就是 dp[i+1][j] 和 dp[i][j+1]，所以遍历的顺序必须保证这两个值是已经算好的。最简单的做法是从最后一行往上遍历、每行从最后一列往左遍历，也就是 i 从 m-1 到 0，j 从 n-1 到 0。这样每次用到 dp[i+1][j]（下一行）和 dp[i][j+1]（本行右侧）的时候，它们都已经成功计算过了，不会出现拿没算过的值凑数的错误。

2. 状态转移方程推导与边界处理

2.1 转移方程是怎么一步步推出来的

如果你站在 (i,j) 这个格子，想知道从这里到终点的最小路径和，首先你必须付出当前格子本身的代价 grid[i][j]。然后你有且只有两个选择：

• 向右走到 (i,j+1)，之后路怎么走就不归你管了，反正由 dp[i][j+1] 告诉你最优的走法。
• 向下走到 (i+1,j)，之后由 dp[i+1][j] 告诉你最优的走法。

你当然要选这两种后续方案里总代价更小的那个。所以转移方程就是：

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

这个式子看起来简单，但你要是真的理解了它，就会发现它天然就把“局部最优”和“全局最优”串起来了：每个格子都只需要管好自己这一步，其余交给子问题。这就是动态规划最让人舒服的地方，你把每个格子的最优值算准确了，答案自然就浮出来了。

2.2 三类边界条件的处理

边界条件是这类二维DP最容易出错的地方。站在最右下角的格子时，你连一步都不用走，所以：

dp[m-1][n-1] = grid[m-1][n-1]

站在最后一行但不在最右列的格子，比如 (m-1, j)，此时你唯一的选择是向右走，因为再往下就出界了。所以：

dp[m-1][j] = grid[m-1][j] + dp[m-1][j+1]

等价于把从 (m-1,j) 到终点一整行的数字累加。站在最后一列但不在最末行的格子，比如 (i,n-1)，唯一选择是向下走，所以：

dp[i][n-1] = grid[i][n-1] + dp[i+1][n-1]

我在刷题的时候犯过一个低级错误：把最后一行和最后一列都写成了固定累加，结果在 1x1 的矩阵上直接越界。1x1 的矩阵只有一个格子，它既是左上角又是右下角，路径和就是 grid[0][0] 本身，处理的时候最好单独捞出来，或者保证通用逻辑能兼容。

2.3 手工推演一个3x3的例子

光说理论不如亲手推一遍。就以刚才那个矩阵为例：

1 3 1 1 5 1 4 2 1

从右下角开始。右下角 dp[2][2] = grid[2][2] = 1。

第二行从右往左推，也就是 (2,1) 和 (2,0)：

• dp[2][1] = grid[2][1] + dp[2][2] = 2 + 1 = 3
• dp[2][0] = grid[2][0] + dp[2][1] = 4 + 3 = 7

第二列从下往上推，也就是 (1,2) 和 (0,2)：

• dp[1][2] = grid[1][2] + dp[2][2] = 1 + 1 = 2
• dp[0][2] = grid[0][2] + dp[1][2] = 1 + 2 = 3

中间值 (1,1)：

• dp[1][1] = grid[1][1] + min(dp[2][1], dp[1][2]) = 5 + min(3, 2) = 7

然后是 (0,1) 和 (1,0)：

• dp[0][1] = grid[0][1] + min(dp[1][1], dp[0][2]) = 3 + min(7, 3) = 6
• dp[1][0] = grid[1][0] + min(dp[2][0], dp[1][1]) = 1 + min(7, 7) = 8

最后是起点 (0,0)：

• dp[0][0] = grid[0][0] + min(dp[1][0], dp[0][1]) = 1 + min(8, 6) = 7

果然得到 7。你可以拿任意一条路径验证，比如 1 → 3 → 1 → 1 → 1，正好就是 7。这种手算的过程我强烈建议新手完整走一遍，它能让你直观感受到每个 dp 值到底代表什么、依赖关系是怎样传导的。我自己带过的几个实习生，凡是认真手推过的，后面写代码基本不会错。

3. 完整代码实现与空间优化

3.1 二维DP数组的直观写法

理解了思路，代码其实很简单。我这里用 Java 写一版最直观的二维 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[m - 1][n - 1] = grid[m - 1][n - 1]; // 最后一行，只能向右走 for (int j = n - 2; j >= 0; j--) { dp[m - 1][j] = grid[m - 1][j] + dp[m - 1][j + 1]; } // 最后一列，只能向下走 for (int i = m - 2; i >= 0; i--) { dp[i][n - 1] = grid[i][n - 1] + dp[i + 1][n - 1]; } // 一般位置 for (int i = m - 2; i >= 0; i--) { for (int j = n - 2; j >= 0; j--) { dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]); } } return dp[0][0]; }

要注意我这里是先单独初始化了最后一行和最后一列，然后才进入双层循环。如果不做这个初始化，循环里 dp[m-1][j+1] 或者 dp[i+1][n-1] 就直接越界了，这是我踩过最多的坑。另一种常见的风格是循环里用 if 判断边界，但那样代码会多出好多分支，反而不好读。我建议就用上面这种，先处理边界，再处理一般情况，逻辑层次分明。

3.2 滚动数组：一维空间的写法与原理

二维 DP 数组的空间复杂度是 O(mn)，在 m 和 n 比较大的时候内存压力不小。但其实每一步我们只用到了下一行的 dp 值和本行右侧的 dp 值，历史行的数据算完之后就再也不会被用到了。这时候就可以用滚动数组，把空间压缩到 O(n)。

怎么压缩？我们用一维数组 dp[j] 来维护“当前行第 j 列”的答案。从下往上遍历 i，每一行内从右往左遍历 j。关键点在于：

• 更新 dp[j] 之前，dp[j] 里存的是下一行第 j 列的旧值，也就是 dp[i+1][j]。
• 更新 dp[j] 之前，dp[j+1] 由于本行还没被覆盖，存的是刚算好的当前行右侧的新值，也就是 dp[i][j+1]。

所以更新公式就是：

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

等一下，这里有个细节要特别说明。当你从右往左更新时，dp[j+1] 已经在当前这一轮被覆盖成新值了，所以 dp[j+1] 就是 dp[i][j+1]；而 dp[j] 还没覆盖，还是下一行同一位置的值 dp[i+1][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; int[] dp = new int[n]; // 从最后一行开始处理 for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (i == m - 1 && j == n - 1) { dp[j] = grid[i][j]; } else if (i == m - 1) { // 最后一行：只能向右 dp[j] = grid[i][j] + dp[j + 1]; } else if (j == n - 1) { // 最后一列：只能向下，dp[j] 还是下一行的值 dp[j] = grid[i][j] + dp[j]; } else { dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]); } } } return dp[0]; }

这种写法对边界的处理也是分成四种情况，逻辑上和白板推演完全一致。还有一种更简洁的写法是把 dp 初始化成最后一行从右往左的累加，然后从倒数第二行开始往上走，但那个写法对新手不够友好，容易绕晕。我写代码的原则是图里清楚第一，空间上已经 O(n) 了，没必要为了少几行 if 牺牲可读性。

3.3 一步到位的原地修改

如果面试官额外问你一句“能不能不用额外空间”，其实这题还能原地做：直接在 grid 数组上改，把 grid[i][j] 覆写成从 (i,j) 到终点的最小路径和。因为每个格子本身只需要读一次、写一次，原地改不影响后续计算，空间复杂度直接变成 O(1)。

实现就是上面一维版本的逻辑，只不过改在二维数组上：

public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (i == m - 1 && j == n - 1) { continue; } else if (i == m - 1) { grid[i][j] += grid[i][j + 1]; } else if (j == n - 1) { grid[i][j] += grid[i + 1][j]; } else { grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]); } } } return grid[0][0]; }

要不要用原地修改，取决于面试的场景。如果是笔试刷题，我更推荐一维滚动数组版本，因为它既展示了空间优化的思考，又不会改动原始输入。如果是面试聊方案，你可以先给二维版本，再主动提“还能用滚动数组优化成 O(n)，甚至原地 O(1)”，这一下就能体现出你对空间复杂度的敏感度。我自己面试别人的时候，听到候选人主动说“这题还能原地改”的时候，好感度是明显上升的。

4. 换个视角：与01背包的动态规划套路对照

4.1 01背包为什么必须从后往前更新

聊到这我想岔开一个话题，因为这个题和 01背包动态规划 在“更新方向”这个点上有一种奇妙的共性，理解了它，你对 DP 的理解会上一个台阶。

01背包问题里，我们用一个一维数组 dp[w] 表示容量为 w 的背包能装的最大价值，遍历每个物品时，容量 w 必须从大到小更新。原因是每个物品只能选一次，如果从小到大更新，dp[w] 用的可能是已经把当前物品放进去之后的 dp 值，相当于当前物品被重复使用了，那就变成了完全背包。

这个“从大到小更新”的本质是什么？就是保证 dp[w] 在更新时，它所依赖的较小的容量 w - weight[i] 还没被当前物品污染，仍然保存着“只考虑前 i-1 个物品”的旧状态。换句话说，你是在用上一轮的旧值推导这一轮的新值，而且你通过遍历顺序天然地保护了旧值不被提前覆盖。

再回头看最小路径和的滚动数组：dp[j] 更新的时候，它依赖的 dp[j+1] 是本轮刚算好的新值（因为 j 从右往左走，j+1 已经被覆盖），而 dp[j] 本身还是下一行的旧值。这里我们利用的同样是“覆盖顺序”来让每个值在需要被读的时候恰好还是我们需要的那一版。

所以两个问题的共同套路是：当你用滚动数组做空间压缩时，遍历方向不是随意定的，它必须保证更新一个状态时，所有依赖状态都还在正确的位置上。这个原则比背任何一道题的题解都重要。

4.2 动态规划中方向选择的通用规律

那怎么快速判断遍历方向对不对？我总结了一个特别简单实用的检查办法：写代码之前，先在纸上把状态转移方程写出来，把每个 dp[i][j] 依赖的其他状态全部圈出来，然后看这些依赖是“二维坐标里的哪个方向”。

如果 dp[i][j] 依赖 dp[i+1][j] 和 dp[i][j+1]（下方和右方），那你遍历的时候 i 必须从大到小、j 必须从大到小，保证依赖值在更新之前已经计算过。这就是题目之所以叫“从下至上”的原因。

如果 dp[i][j] 依赖 dp[i-1][j] 和 dp[i][j-1]（上方和左方），那 i 从小到大、j 从小到大，正向推就行。这也是很多题解选择正向推的原因，因为它在脑内符合“从起点出发”的直觉。

如果 dp[i][j] 同时依赖四个方向，那普通的逐行遍历就不适用了，得考虑记忆化搜索，或者多次迭代直到收敛。这种题目复杂度明显更高，不是今天的重点。

理解了这套规律，你以后再看到任何二维 DP 题，第一反应就不再是背模板，而是先画依赖图，再定遍历顺序。01背包、完全背包、最小路径和、不同路径、最长公共子序列，全都是这套底层规则在起作用。

5. 常见问题与排查技巧实录

5.1 数组越界与初始化问题

我刷题的时候，包括给同事做 code review 的时候，最常见的问题就是边界越界。特别是最后一行和最后一列没有单独初始化就直接进入双层循环，一跑就报 ArrayIndexOutOfBoundsException。

还有个更隐蔽的坑是 dp 数组初始化成 0。比如你从下至上推的时候，如果某个格子是普通位置，方程是 grid[i][j] + min(dp[i+1][j], dp[i][j+1])，这时候万一 dp 数组里没填到的位置是 0，那 min 的结果会被 0 干扰，算出来的值莫名其妙地小。这个问题在从下至上的写法里相对少见，因为最右下角肯定先初始化了；但在有些变体题里，你需要把 dp 数组初始化成 Integer.MAX_VALUE 才能保证 min 运算不受“无效值”影响。

我建议拿到任何 DP 题，先问自己三个问题：

• 初始值应该是什么？哪些状态是已知的？
• 哪些状态是无效的？无效值应该初始化为多少才不会干扰计算？
• 遍历的顺序是什么？依赖关系有没有被破坏？

这三个问题想清楚，代码基本不会错。

5.2 遍历方向写错导致答案怪异

还有一次我看到一个同学实现这题，用的也是从下至上，但内层循环 j 从 0 到 n-1 正向走。结果他 dp[j+1] 的值还没算出来，他就拿来用了，导致答案完全不对。

这种问题特别容易出现在“看着原理懂了，动手就写反”的人身上。排查办法很简单：找一个 2x2 的小矩阵手动跑一遍流程，用笔在纸上标记每个 dp 值的计算顺序，一旦发现某个依赖值还没有被算出来，就是遍历方向写错了。我自己的习惯是，写完代码不急着提交，先跑一个 3x3 的样例，追踪每一步的结果，确认和手算一致再提交。这一步在笔试的时候特别救命。

5.3 面试追问：如果还要输出最短路径怎么办

有些面试官不满足于只返回最小路径和，还会追加一句“那你把最短路径给我打出来看看”。这时候需要额外记录每个格子的决策方向。我们可以开一个二维数组 path，在转移的时候记录从哪个方向走来的。因为从下至上推导，起点是右下角，方向可能写成“从 (i,j) 走到了 (i+1,j) 还是 (i,j+1)”，最后从 (0,0) 开始顺着方向拼出整条路径。

也可以简化处理：算出 dp 数组之后，从 (0,0) 沿着 min(dp下方, dp右方) 的方向走，每走一步就记录当前格子。因为 dp 值已经包含了完整的全局信息，这时候贪心地选择值更小的方向走，必然是正确的。这个方式不需要额外记录空间，只是需要保留 dp 数组。如果之前为了优化空间把 dp 压缩成了一维，那输出路径的时候就需要回退到二维版本，或者额外记录路径信息了。这就是空间优化带来的一个小代价，面试时可以主动提一句，展示你对权衡的理解。

5.4 变体场景：带障碍物、带初始血量的题目

矩阵最小路径和这个模型非常经典，很多题都是它的变体。比如某些版本里格子值是正数和负数混合，路径和可能为负，这时候初始化就不再是 0 的问题，而要考虑负数的存在；再比如某些版本里某些格子不能走，相当于障碍物，那你需要在转移的时候跳过这些格子，把它们设为正无穷。

还有个有趣变体是“地下城游戏”，要求骑士从左上走到右下，血量不能为负，求初始最少血量。这道题如果用正向推会非常痛苦，因为你不知道未来的消耗，但用从下至上的倒推就顺畅很多：dp[i][j] 表示进入 (i,j) 前至少要有多少血，才能保证走到终点。这种“从终点反向推起点”的思路，本质和最小路径和一模一样。所以我说这题值得吃透，它是一把钥匙，打开的不止是一道题。

6. 基于实操经验的完整刷题建议

最后分享一点我这几年刷题、带新人总结下来的体感经验。很多人遇到矩阵动态规划第一反应就是套模板，我觉得最有效的方式是：先别看题解，自己在纸上画一个 3x3 的矩阵，试着用递归的想法写一个暴力版本，然后从暴力版本的“重复子问题”里找到 DP 的切入点。

拿这题举例，用递归去想的话：从 (i,j) 到终点的最小路径 f(i,j) = grid[i][j] + min(f(i+1,j), f(i,j+1))。你画出递归树之后会发现，f(1,1) 这种子问题被反复计算了好多次，于是毫不犹豫地加个缓存，这就变成记忆化搜索；再把递归展开成迭代，就是动态规划。从暴力到记忆化再到 DP 的路径，比直接死记状态转移方程要牢靠得多。

我当时在实际刷这题的时候，最先写的是记忆化搜索，因为那是最符合直觉的：从终点递归，每次把结果存下来。然后我才改成迭代的从下至上版本，把递归栈彻底去掉。如果你觉得递归不好理解，可以先写记忆化搜索，再把递归改成循环，很多 DP 难题都能用这条路线啃下来。

这种“先递归后迭代”的路径也让我意识到，动态规划并不是什么高深莫测的魔法，它本质就是暴力搜索加缓存，然后再把缓存的计算顺序理清楚。有了这个认知，遇到新题就不慌了：先写递归，再优化，总能做出来。

如果你正在准备面试，我建议把这道题和不同路径、01背包、最长递增子序列这四道题放在一起对比着做。它们几乎是动态规划所有典型套路的浓缩：二维网格、组合计数、背包优化、一维线性。吃透这四个模型，面试里遇到动态规划题，你至少能想出个七七八八。