LeetCode 931中等二维动态规划
下降路径最小和 图解题解
这道题到底在问什么
给一个 n×n 矩阵 matrix。从第一行任意一格开始下落，每次只能落到正下方、左下方或右下方那一格，一直落到最后一行。求所有下降路径里，路径上数字之和最小的那个。
- matrix
- [[2,1,3,4],[6,5,4,2],[7,8,1,9],[5,2,3,8]]
- 输出
- 8
- 一条最优路
- 1 → 4 → 1 → 2 = 8
先想最直接的笨办法
与其重复枚举每条路，不如把每个格子的最小代价记进一张表。递推式：dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。「到 (i,j) 的所有路」按最后一步从哪格下来，不重不漏分成三类，三格早算好了——直接查表取最小，绝不重算。（动画第 6 步）
最优解：一步一步想明白
- 3先别急着写代码，想想到底有多少条路。
- 4最直接的想法：把每条可能的下降路都走一遍，算出和，取最小。逻辑没错，但慢。每往下一行最多分叉 ×3，路径数接近 3ⁿ，根因是同一个格子被无数条路反复经过、反复重算。
- 5要落到格子 (i,j)，上一步只可能站在它正上方 (i-1,j)、左上 (i-1,j-1) 或右上 (i-1,j+1) 这三格之一。所以「到 (i,j) 的最小和」= 这三格里最小的那个，再加上 (i,j) 自己。
- 6与其重复枚举每条路，不如把每个格子的最小代价记进一张表。递推式：dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。「到 (i,j) 的所有路」按最后一步从哪格下来，不重不漏分成三类，三格早算好了——直接查表取最小，绝不重算。
- 74×4 · 第一行直接拷 matrix建一张和矩阵一样大的 4×4 表，dp[i][j] 存「落到这格的最小路径和」。第一行就是起点，没有上一步，所以 dp[0][j] 直接等于 matrix[0][j]：2, 1, 3, 4。下面一格一格往下填。
- 8最左 · 只有 正上 / 右上先填行1。第0格在最左边，没有左上那一格，只能从正上(2)或右上(1)落下来。先把这两个来源高亮出来，看清能从哪里走过来。
- 96 + min(2,1) = 7正上 2、右上 1，取最小 1，加上自己 matrix=6 → dp[1][0] = 7。左边界要小心：少看一个方向。
- 10中间 · 上方三格齐全第1格在中间，上方三格全有：左上2、正上1、右上3。先把三个来源高亮出来——这就是「三选一取最小」的标准情形。
- 11中间 · 上方三格齐全三个来源里最小是正上的 1，加自己 5 = 6。
- 12中间 · 上方三格齐全第2格也在中间，左上1、正上3、右上4，最小是左上的 1，加自己 4 = 5。
- 13最右 · 只有 左上 / 正上第3格在最右边，没有右上，只能从左上(3)或正上(4)落下来。取最小 3，加自己 2 = 5。行1 填完：[7, 6, 5, 5]。右边界同样要少看一个方向。
- 14注意：填行2时，我们只关心行1的 dp 值 7/6/5/5，完全不用管它们是怎么来的。这就是 DP 省时间的根本——上一行的最优结果被缓存住了。
- 15最左 · 无左上开始填行2。第0格在最左边，没有左上，来源只有正上(7)和右上(6)，先把这两个来源高亮。
- 16最左 · 无左上正上7、右上6，取最小 6，加自己 matrix=7 = 13。
- 17中间 · 三格齐全填行2第1格 matrix=8。上方三格 7/6/5 都有，最小是右上的 5，加自己 8 = 13。
- 18中间 · 三格齐全填行2第2格 matrix=1。上方三格 6/5/5，最小 5，加自己 1 = 6。这个很小的 6 待会儿是最优路上的关键一站。
- 19最右 · 无右上填行2第3格 matrix=9。最右边没有右上，从左上(5)或正上(5)落下，取最小 5，加自己 9 = 14。行2 填完：[13, 13, 6, 14]。
- 20最左 · 无左上填最后一行第0格 matrix=5。最左边没有左上，从正上(13)或右上(13)落下，取最小 13，加自己 5 = 18。
- 21中间 · 右上有个小 6填行3第1格前，先看它的上方三格：左上13、正上13、右上只有 6。一眼就知道该斜接到那个小 6 上。
- 22中间 · 右上的小 6 救场最小是右上的 6，加自己 matrix=2 = 8。它没走两个 13，而是斜接到那个小 6 上，这就是 DP 自动挑出的便宜路。
- 23中间 · 三格齐全填最后一行第2格 matrix=3。上方三格 13/6/14，最小是正上的 6，加自己 3 = 9。
- 24最右 · 无右上填最后一行第3格 matrix=8。最右边没有右上，从左上(6)或正上(14)落下，取最小 6，加自己 8 = 14。最后一行填完：[18, 8, 9, 14]。
- 25答案 = min(18,8,9,14) = 8下降路径可以停在最后一行任意一格，所以答案是最后一行 dp 值里最小的那个：min(18,8,9,14) = 8，落在列1。别只盯某一列。
- 261 → 4 → 1 → 2 = 8从末行最小处 dp[3][1]=8 反向回溯：它从右上 6 来 → 6 是 dp[2][2] 从正上 5 来 → 5 是 dp[1][2] 从左上 1 来 → 1 是 dp[0][1]。对应原矩阵 1 → 4 → 1 → 2，正好加起来 8。
- 27每个格子只算一次、每次只看上方三格，总共 n² 次小计算就出答案，比指数级暴力快出几个数量级。
- 30不同路径那题求「有几条路」，要把上、左两格的方案数加起来；本题求「最小代价」，要在上方三格里挑一个最便宜的接上来。看清是「计数」还是「最优」，递推式就不会写反。
- 31三角形最小路径和、不同路径 II、最小路径和，骨架都是这一套：定义 dp[i][j]，找清楚它能从哪几格转移过来，取最优。
- 33j=0 访问 dp[i-1][-1] → 越界!填最左列 (i,0) 时，左上是 (i-1,-1)，根本不存在。不加 j>0 判断，Python 会取到上一行末尾的错值、C++/Java 直接越界崩。所以边界判断不是可有可无。
⚠️ 容易写错的地方
✗ 错：在最左/最右列也去访问左上或右上
✓ 对：j>0 才看左上、j<n-1 才看右上
j-1 或 j+1 会越界，导致数组下标错误
✗ 错：只返回 dp[n-1][0] 或某一固定列
✓ 对：返回最后一行所有 dp 值的最小
下降路径可以停在末行任意一格
✗ 错：把 min 写成 sum 或漏掉某个方向
✓ 对：在三个(边界两个)合法来源里取 min
求的是最小代价，不是路径条数，也不能漏方向
完整代码（Python / C++ / Java）
Python
class Solution:
def minFallingPathSum(self, matrix):
n = len(matrix)
dp = list(matrix[0]) # 第一行就是起点
for i in range(1, n):
cur = [0] * n
for j in range(n):
best = dp[j] # 正上方
if j > 0:
best = min(best, dp[j - 1]) # 左上
if j < n - 1:
best = min(best, dp[j + 1]) # 右上
cur[j] = matrix[i][j] + best
dp = cur
return min(dp) # 最后一行最小值C++
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<int> dp = matrix[0]; // 第一行起点
for (int i = 1; i < n; i++) {
vector<int> cur(n);
for (int j = 0; j < n; j++) {
int best = dp[j]; // 正上方
if (j > 0) best = min(best, dp[j - 1]); // 左上
if (j < n - 1) best = min(best, dp[j + 1]); // 右上
cur[j] = matrix[i][j] + best;
}
dp = cur;
}
return *min_element(dp.begin(), dp.end());
}
};Java
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[] dp = new int[n];
for (int j = 0; j < n; j++) dp[j] = matrix[0][j]; // 第一行起点
for (int i = 1; i < n; i++) {
int[] cur = new int[n];
for (int j = 0; j < n; j++) {
int best = dp[j]; // 正上方
if (j > 0) best = Math.min(best, dp[j - 1]); // 左上
if (j < n - 1) best = Math.min(best, dp[j + 1]); // 右上
cur[j] = matrix[i][j] + best;
}
dp = cur;
}
int ans = dp[0];
for (int j = 1; j < n; j++) ans = Math.min(ans, dp[j]);
return ans;
}
}复杂度
时间复杂度
O(n²)
矩阵 n×n 共 n² 个格子，每格只算一次、每次看上方三格(常数次) → O(n²)
空间复杂度
O(n)
只需保存上一行的 dp 值(一行 n 个)滚动更新；若直接开 n×n 表则 O(n²)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 下降路径最小和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
空间能优化到 O(n) 吗?+
能。dp[i][j] 只依赖上一行，所以只保存一行、滚动更新即可，把 O(n²) 表压成 O(n)。
为什么这题适合用 DP 而不是贪心?+
贪心每步取局部最小可能走进死路，全局并非最优；DP 把每格的全局最优都缓存下来，保证最终最小。
如果还要输出具体路径怎么办?+
填表时额外记下每格是从上方哪一格转移来的(parent)，到末行最小处反向回溯即可还原路径。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 下降路径最小和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。