刷算法题有一段时间的人大概率会碰到这么一道经典题给你一个二维矩阵从左上角走到右下角每次只能向右或者向下走一格求路径上所有数字之和的最小值。牛客上这道题编号是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,j1)或者下边的格子 (i1,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[i1][j] 和 dp[i][j1]所以遍历的顺序必须保证这两个值是已经算好的。最简单的做法是从最后一行往上遍历、每行从最后一列往左遍历也就是 i 从 m-1 到 0j 从 n-1 到 0。这样每次用到 dp[i1][j]下一行和 dp[i][j1]本行右侧的时候它们都已经成功计算过了不会出现拿没算过的值凑数的错误。2. 状态转移方程推导与边界处理2.1 转移方程是怎么一步步推出来的如果你站在 (i,j) 这个格子想知道从这里到终点的最小路径和首先你必须付出当前格子本身的代价 grid[i][j]。然后你有且只有两个选择向右走到 (i,j1)之后路怎么走就不归你管了反正由 dp[i][j1] 告诉你最优的走法。向下走到 (i1,j)之后由 dp[i1][j] 告诉你最优的走法。你当然要选这两种后续方案里总代价更小的那个。所以转移方程就是dp[i][j] grid[i][j] min(dp[i1][j], dp[i][j1])这个式子看起来简单但你要是真的理解了它就会发现它天然就把“局部最优”和“全局最优”串起来了每个格子都只需要管好自己这一步其余交给子问题。这就是动态规划最让人舒服的地方你把每个格子的最优值算准确了答案自然就浮出来了。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][j1]等价于把从 (m-1,j) 到终点一整行的数字累加。站在最后一列但不在最末行的格子比如 (i,n-1)唯一选择是向下走所以dp[i][n-1] grid[i][n-1] dp[i1][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 3dp[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 2dp[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) 6dp[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][j1] 或者 dp[i1][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[i1][j]。更新 dp[j] 之前dp[j1] 由于本行还没被覆盖存的是刚算好的当前行右侧的新值也就是 dp[i][j1]。所以更新公式就是dp[j] grid[i][j] min(dp[j], dp[j 1])等一下这里有个细节要特别说明。当你从右往左更新时dp[j1] 已经在当前这一轮被覆盖成新值了所以 dp[j1] 就是 dp[i][j1]而 dp[j] 还没覆盖还是下一行同一位置的值 dp[i1][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[j1] 是本轮刚算好的新值因为 j 从右往左走j1 已经被覆盖而 dp[j] 本身还是下一行的旧值。这里我们利用的同样是“覆盖顺序”来让每个值在需要被读的时候恰好还是我们需要的那一版。所以两个问题的共同套路是当你用滚动数组做空间压缩时遍历方向不是随意定的它必须保证更新一个状态时所有依赖状态都还在正确的位置上。这个原则比背任何一道题的题解都重要。4.2 动态规划中方向选择的通用规律那怎么快速判断遍历方向对不对我总结了一个特别简单实用的检查办法写代码之前先在纸上把状态转移方程写出来把每个 dp[i][j] 依赖的其他状态全部圈出来然后看这些依赖是“二维坐标里的哪个方向”。如果 dp[i][j] 依赖 dp[i1][j] 和 dp[i][j1]下方和右方那你遍历的时候 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[i1][j], dp[i][j1])这时候万一 dp 数组里没填到的位置是 0那 min 的结果会被 0 干扰算出来的值莫名其妙地小。这个问题在从下至上的写法里相对少见因为最右下角肯定先初始化了但在有些变体题里你需要把 dp 数组初始化成 Integer.MAX_VALUE 才能保证 min 运算不受“无效值”影响。我建议拿到任何 DP 题先问自己三个问题初始值应该是什么哪些状态是已知的哪些状态是无效的无效值应该初始化为多少才不会干扰计算遍历的顺序是什么依赖关系有没有被破坏这三个问题想清楚代码基本不会错。5.2 遍历方向写错导致答案怪异还有一次我看到一个同学实现这题用的也是从下至上但内层循环 j 从 0 到 n-1 正向走。结果他 dp[j1] 的值还没算出来他就拿来用了导致答案完全不对。这种问题特别容易出现在“看着原理懂了动手就写反”的人身上。排查办法很简单找一个 2x2 的小矩阵手动跑一遍流程用笔在纸上标记每个 dp 值的计算顺序一旦发现某个依赖值还没有被算出来就是遍历方向写错了。我自己的习惯是写完代码不急着提交先跑一个 3x3 的样例追踪每一步的结果确认和手算一致再提交。这一步在笔试的时候特别救命。5.3 面试追问如果还要输出最短路径怎么办有些面试官不满足于只返回最小路径和还会追加一句“那你把最短路径给我打出来看看”。这时候需要额外记录每个格子的决策方向。我们可以开一个二维数组 path在转移的时候记录从哪个方向走来的。因为从下至上推导起点是右下角方向可能写成“从 (i,j) 走到了 (i1,j) 还是 (i,j1)”最后从 (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(i1,j), f(i,j1))。你画出递归树之后会发现f(1,1) 这种子问题被反复计算了好多次于是毫不犹豫地加个缓存这就变成记忆化搜索再把递归展开成迭代就是动态规划。从暴力到记忆化再到 DP 的路径比直接死记状态转移方程要牢靠得多。我当时在实际刷这题的时候最先写的是记忆化搜索因为那是最符合直觉的从终点递归每次把结果存下来。然后我才改成迭代的从下至上版本把递归栈彻底去掉。如果你觉得递归不好理解可以先写记忆化搜索再把递归改成循环很多 DP 难题都能用这条路线啃下来。这种“先递归后迭代”的路径也让我意识到动态规划并不是什么高深莫测的魔法它本质就是暴力搜索加缓存然后再把缓存的计算顺序理清楚。有了这个认知遇到新题就不慌了先写递归再优化总能做出来。如果你正在准备面试我建议把这道题和不同路径、01背包、最长递增子序列这四道题放在一起对比着做。它们几乎是动态规划所有典型套路的浓缩二维网格、组合计数、背包优化、一维线性。吃透这四个模型面试里遇到动态规划题你至少能想出个七七八八。