拓冰网站定制 
1. 题目拆解与动态规划思路的来源“下降路径最小和”这道题熟面孔了。LeetCode 第 931 题属于那种“必刷基础算法题”里的常青树尤其适合刚把动态规划提上日程的选手热身。它的原型问题其实是更经典的“最小路径和”LeetCode 64只不过把走法从“右 / 下”换成了“左下方 / 正下方 / 右下方”方向感一变很多人的状态定义思路就卡壳了。题目描述我先复述一下给定一个 n x n 的整数矩阵从第一行任意位置出发每次只能向下移动到下一行的相邻列即正下方、左下方、右下方走到最后一行时把路径经过的所有数字加起来要求这个和是最小的。注意几个关键字“第一行任意位置”、“每次只能向下走一行”、“可选的列偏移只有 -1、0、1”、“求最小和”。这几个关键字基本把解法锁死了——就是动态规划。为什么第一反应必须是 DP 而不是 DFS 或回溯因为每一步的选择都会影响后续所有走法暴力枚举所有路径是指数级的n 稍微给到 30 以上就废了。而它的决策结构又恰好满足“重叠子问题”和“最优子结构”从顶部走到 (i, j) 这个格子的最小和只与能从哪个格子走下来有关走到那个格子的最小和又只与其上方几格有关。层层递推最终答案肯定藏在“走到最后一行时所有格子的最小路径和”里取最小值。状态定义其实有两套思路。一种是从上往下推dp[i][j] 表示“从第一行任意位置出发到达第 i 行第 j 列时路径上数字和的最小值”。另一种是从下往上推dp[i][j] 表示“从第 i 行第 j 列出发走到最后一行的最小路径和”。这两种定义代码写出来大同小异但思路的出发点完全不同。我推荐从上往下推因为它的边界初始化更直观——第一行的 dp 值就直接等于矩阵第一行的值然后从第二行开始递推。转移方程长这样dp[i][j] matrix[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j1])其中只有 j 越界的那两个方向需要特殊处理。这方程本质上是在说你想到达 (i, j) 这一格合法前驱只可能是上一行的 j-1、j、j1 三个位置选它们之中走过来的最小路径和再把自己这一格的数字累加上去。生活化地理解就像你在爬一座金字塔形的阶梯每层只能从左、中、右三块立足点中挑一个落脚想知道踩到某一格子的最小体力消耗就看前一步选哪块砖最省劲。我见过有人在这道题上绕进另一个思路——把矩阵旋转 45 度当成三角形来做。原题太经典没必要这么折腾。老老实实开一个二维 dp 数组或者更进一步用一个一维数组滚动更新这道题的复杂度就能压到 O(n^2) 时间、O(n) 空间是面试官最乐意看到的形态。2. 三种主流语言实现与细节对比2.1 Python 版本用切片规避边界判断Python 写这种矩阵 DP 题代码量可以压得很薄。我先把最朴素的二维数组版本贴出来方便和后续一维优化做对比def minFallingPathSum(matrix): n len(matrix) if n 1: return matrix[0][0] # dp[j] 表示到达上一行第 j 列的最小路径和 dp matrix[0][:] for i in range(1, n): new_dp [0] * n for j in range(n): # 三个前驱中取最小注意 j0 和 jn-1 时边界 candidates [dp[k] for k in (j-1, j, j1) if 0 k n] new_dp[j] matrix[i][j] min(candidates) dp new_dp return min(dp)这个版本里有一个细节很多人初学时会漏掉dp matrix[0][:]必须带上切片符号[:]。如果直接写dp matrix[0]那么后续修改 dp 会直接改掉 matrix 的第一行虽然在当前这个算法流程里不至于引发致命错误但一旦你在同一个题解里同时维护多个变量很容易埋下数据污染的坑。切片复制是 Python 程序员的基本素养这里顺便养成就好。另外我用了一个列表推导式[dp[k] for k in (j-1, j, j1) if 0 k n]来优雅地过滤越界下标。这个写法在 Python 里很常用但是要强调一下性能问题每计算一个格子都要临时构造一个列表再取 min对于 n100 的规模完全无所谓但如果哪天刷到 n1000 以上的变体题这个列表推导式的开销会拖慢速度。那种极端情况下手动展开成 if-else 判断三个候选会更稳妥。那三行基础面试代码用这个解法已经够用了。我更喜欢 Python 版的原因在于它可以完全脱离显式边界判断把注意力集中在转移方程本身的逻辑上。这对初学者看代码时理解状态转移是有帮助的——不会被if j 0之类的分支打乱思路。2.2 Java 版本边界条件需要显式处理Java 没法像 Python 那样用切片优雅地过滤越界下标所以边界条件靠 if 判断来兜底。我建议写这种时候不要贪图代码简短按最直白的方式写反而容易对class Solution { public int minFallingPathSum(int[][] matrix) { int n matrix.length; if (n 1) { return matrix[0][0]; } 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[] newDp new int[n]; for (int j 0; j n; j) { int minPrev dp[j]; // 正上方 if (j 0) { minPrev Math.min(minPrev, dp[j - 1]); // 左上方 } if (j n - 1) { minPrev Math.min(minPrev, dp[j 1]); // 右上方 } newDp[j] matrix[i][j] minPrev; } dp newDp; } int ans Integer.MAX_VALUE; for (int val : dp) { ans Math.min(ans, val); } return ans; } }这里有一个容易写错的点是Math.min的嵌套顺序。有些初学者习惯先把三个候选都存入一个数组或者 list 里再遍历取最小值这在 Java 里不仅多此一举还会在n较大时产生不必要的对象分配。直接两两比较两次即可性能最好。另外if (n 1)这个特判不能删。矩阵只有一行时min(dp)也能返回正确结果但如果你在更复杂的变体题里忽略了这个边界后续访问matrix[i - 1]就可能数组越界。与其依赖后续逻辑偶然正确不如开局就把它堵死。Java 版的面试写法我还推荐在类名上直接用Solution这样在任何 OJ 平台上直接粘贴就能跑不用额外调整。有同行问我为什么不在主函数里加测试用例我的观点是刷算法题的核心是把核心逻辑写清楚评测逻辑留给平台跑本地调试时再去补 main 方法即可。2.3 C 版本注意数据溢出和内存布局C 版本的思路和 Java 完全一致但要注意一个语言本身的坑——矩阵里的元素范围是[-100, 100]n 最大到 100所以路径和的理论极限在-10000到10000之间用int完全够。但如果哪天题目改成元素范围更大或者 n 更大就要考虑用long long接收求和结果否则容易溢出。这是比赛里出题人最喜欢藏的陷阱。class Solution { public: int minFallingPathSum(vectorvectorint matrix) { int n matrix.size(); if (n 1) { return matrix[0][0]; } vectorint dp(matrix[0].begin(), matrix[0].end()); for (int i 1; i n; i) { vectorint newDp(n, 0); for (int j 0; j n; j) { int minPrev dp[j]; if (j 0) { minPrev min(minPrev, dp[j - 1]); } if (j n - 1) { minPrev min(minPrev, dp[j 1]); } newDp[j] matrix[i][j] minPrev; } dp.swap(newDp); } return *min_element(dp.begin(), dp.end()); } };用vectorint dp(matrix[0].begin(), matrix[0].end())做初始化比直接 matrix[0]更安全因为这相当于按值拷贝一行而不是共享底层数据。dp.swap(newDp)是 C 里常见的滚动数组替换方式它只交换两个 vector 的内部指针不涉及整块内存拷贝性能开销极低。最后求答案用的*min_element需要#include algorithm如果你是在 LeetCode 风格的环境下做题系统已经帮你引入了标准库不需要自己写头文件。但如果这个代码要移到本地编译就必须记得补上头文件。这种细节平时不显眼面试现场忘了写或者写错可能会给面试官留下基本功不扎实的印象。3. 空间优化与状态压缩思路3.1 为什么可以优化递推只依赖前一行很多算法题教程会直接告诉你“可以压缩到一维数组”但不说为什么。这道题里我们先看递推关系计算第 i 行的 dp 值只需要用到第 i-1 行的 dp 值再往上的行已经彻底用不到了。用流程图想一下就是逐层覆盖的节奏。类比来说你在记“走到每一格的当前最小和”时就像一个记账本每一页只记录上一层的读数。当你翻到新的一层时老的一层数据已经没有查询价值了直接擦掉重写就行。基于这个观察二维 dp 数组可以压缩成两个一维数组dp存上一行结果newDp存当前行结果。这是空间优化里最稳妥的“滚动数组”方案你永远不会读到被覆盖的旧值。上面三种语言的实现用的正是这种双一维数组方案从空间复杂度来讲已经从 O(n^2) 降到了 O(n)。3.2 只用一个数组的进阶玩法原地更新与覆盖顺序如果你想把空间压到极致可以用一个数组dp在遍历 j 的过程中直接原地更新。但这么做有一个非常关键的坑计算dp[j]时需要读到dp[j-1]的旧值上一行的值如果 j 从左往右遍历dp[j-1]已经被更新成当前行的新值了那就坏了。所以原地更新必须额外用一个变量暂存“即将被覆盖的旧值”类似滚动数组里常见的temp保存操作。伪代码大概是for i in range(1, n): temp dp[0] # 保存上一行 j0 的旧值 dp[0] matrix[i][0] min(dp[0], dp[1]) for j in range(1, n): # 此时 temp 保存的是上一行 j-1 的旧值dp[j] 还没被覆盖是上一行的旧值 # dp[j1] 也还是上一行的旧值 old dp[j] # 保存当前 dp[j] 的旧值供下一轮 j1 使用 dp[j] matrix[i][j] min(temp, dp[j], dp[j1] if j 1 n else large) temp old这段代码虽然行数多、心累但省下的那一个数组在绝大多数真实的 OJ 环境中已经没有明显价值了——毕竟 n 撑死 100。我个人的建议是面试时写两个数组的版本既清晰又不容易出错把“我能理解一数组原地更新的覆盖顺序”作为口头补充回答即可。真手写出 bug 了得不偿失。3.3 复杂度对比从 O(n^2) 空间到 O(1) 空间这里顺带把三种空间方案的对比整理一下方便你理解为什么优化是值得的方案空间复杂度优点缺点完整二维 dp 数组O(n^2)每个格子的路径和均可回溯占内存n 大时浪费两个一维数组滚动O(n)逻辑清晰、不易出错多一次数组拷贝可优化为交换单数组原地覆盖O(1)空间最省覆盖顺序处理复杂边界易错时间复杂度的底线是 O(n^2) 无论如何无法再降——因为你至少要遍历矩阵里每个格子一次。这个下界很多人会忽略面试时如果被问“还能不能更快”你可以理直气壮地说不能因为输入本身就有 n^2 个数据要处理。还有一个值得说明的点Java 和 C 里两个数组滚动时newDp每次 new 一个长度为 n 的数组对于 n100 来说毫无压力。但如果你把这道题的变体扩展到 n10^5矩阵从方形变成超宽那每一行都 new 新数组的开销就会比较明显此时应该考虑在循环外预先分配两块数组然后用swap交替使用避免频繁申请内存。4. 常见问题与排查技巧实录4.1 问题一边界下标导致数组越界这是我收到提问最多的问题尤其是第一次写 Java 和 C 版本的同学。每次循环里dp[j-1]在 j0 时直接变成dp[-1]直接抛ArrayIndexOutOfBoundsException或触发未定义行为。Python 虽然不会立刻报错但dp[-1]会取到数组最后一个元素结果就变成了“用下一行的值来算当前行”答案自然全错。排查技巧先把矩阵缩小到 2x2手动在纸上把每一次循环的 j、dp 值、newDp 值都推算一遍。这种小规模手工推演比在代码里打日志更直观也更能训练你建立状态转移的直觉。真正理解了“j-1 和 j1 分别会在哪些位置越界”之后再回头看代码里的 if 条件就会觉得那是顺理成章的写法。4.2 问题二一维数组更新时读到了当前行的新值如果你尝试把双数组改写成单数组最常见的结果就是答案偏大或偏小且错误随机分布。原因在于更新dp[j]时右边的dp[j-1]可能已经是当前行的新值破坏了“只能依赖上一行”的前提。这不是算法思路错误而是数据更新顺序导致的逻辑污染。我建议在调试这种错误时打印每一行更新后的 dp 数组和正确结果对比一下你会发现从某一行开始某一个格子的值出现诡异跳变。顺着这个格子的依赖链回溯很快就能定位是变量覆盖顺序的问题。4.3 问题二点五初始化时误用 0 或 Integer.MIN_VALUE矩阵里的数字可能全是负数此时用 0 作为 dp 初始值会导致任何负数的真实路径和都被错误地忽略。典型的错误是dp [0] * n如果第一行就有负数这个初始化会让后续所有正数路径的计算产生错误的最小值判断。标准做法是第一行直接用matrix[0]初始化 dp不需要额外填充极值。或者在更通用的模板里用一个大数比如10**9或Integer.MAX_VALUE / 2填充 dp再单独处理第一行。这里要注意用MAX_VALUE / 2而不是MAX_VALUE因为后面有 matrix[i][j]直接用MAX_VALUE可能会溢出变成负数反倒干扰取最小值。4.4 问题三只有一行或一列的特殊输入n1 时循环从 i1 开始就不会执行最后min(dp)其实就是dp[0]即matrix[0][0]——所以即使不特判结果也对。但如果是“只有一列”的矩阵呢题目会强调是 n x n所以一列的情况不存在。但很多变体题会改成 m x n 矩形此时若 n1转移时就不能取j1和j-1需要特判。我的建议是模板里把n 1提前返回这不仅是为了正确性更是提醒你自己这道题的最简输入形态是什么。4.5 问题四误以为必须从 (0,0) 出发答案只查 dp[n-1][n-1]这道题和“最小路径和”最大的区别就是起点和终点不固定。起点可以是第一行任意列终点可以是最后一行任意列。很多人把 64 题的代码改一改就套过来算出的却是从左上角到右下角的最小路径和答案自然不对。正确做法的收尾是取min(dp)最后一行的所有值中的最小值而不是dp[n-1]。面试时这个小小的差异就是区分“背模板”和“理解题意”的关键信号。我建议在写完代码后自己在注释里写清楚这个题解的终点不固定所以答案在最后一行取 min不要默认最后一行的最后一个元素。4.6 问题五原地修改 matrix 的偏好有人为了省一个数组直接在 matrix 上累加 dp 值。这个思路理论上没问题——因为第 i 行只会被读一次第 i 行的原始值之后不再需要了。但我不推荐这么写。原因一修改输入数据不是好习惯万一之后面试官追加问你“如何打印出最小路径的完整轨迹”你就无法依赖原始矩阵了原因二在 Debug 时保留原始矩阵能帮你随时核对每一步计算结果。清晰的代码永远比省一点内存更重要。4.7 排查思路速查表症状可能原因排查顺序j 从 0 开始却报数组越界踩到 dp[j-1] 或 matrix[i][j-1]检查 j 是否等于 0结果偏大初始值设成了 0 或正数忽略了负数路径检查 dp 初始化方式结果偏小且逐行漂移单数组覆盖顺序错误打印每轮 dp 对比只在 n1 时报错没有处理单行矩阵的边界入口直接加特判答案明显错但递推没问题终点取错了位置确认收尾取 min(dp)5. 变体与延伸从这道题拓展到一类问题5.1 变体一三角形最小路径和LeetCode 120 题“三角形最小路径和”是这道题最出名的同门兄弟。它把矩形换成了阶梯形排列转移方程从min(dp[i-1][j-1], dp[i-1][j])变成了只有左和右两个方向。思路、代码、优化手段几乎完全一致。刷完下降路径最小和接着刷 120连续两道题下来你对“走格子的 DP”基本就有肌肉记忆了。5.2 变体二矩形网格的上下左右四方向移动如果题目改成“允许左右移动并可以向上”那就变成了更复杂的图论最短路问题需要用 Dijkstra 或 BFS 来解DP 的简单递推已经失效。这个区分非常重要——写题前先看限制条件移动方向是单向还是双向是只能向下还是可以回头决定了整个解法的类别。我见过很多人把题目稍一变形就强行套 DP结果越套越乱。正确的方法论是先分析递推依赖的方向性如果状态之间只有单向依赖且无环DP 才成立一旦可能出现循环依赖就得换算法。5.3 变体三要求输出路径本身而不只是最小值原题只要最小和但面试官经常会追加一句——“你能不能把那条路径给我打印出来”这时就需要额外开一个 parent 数组在更新 dp 的同时记录每个格子是从哪个前驱走来的最后从最后一行最小值对应的格子回溯到第一行。这个技巧虽然简单但如果没有在写第一版代码时就预留后续重构会比较痛苦。我建议在平时练习时就做好习惯dp 初始化和转移时顺手在另一个数组里记录“上一行选择的列”。虽然原题没要求但这个扩展在小厂面试里出现的频率不低。把基础逻辑写扎实追加深挖时你才有余裕。5.4 变体四大规模矩阵下的内存优化当 n 到达 1000 或者更大时O(n^2) 的空间可能触碰内存限制。此时单数组原地覆盖就是迫不得已的选择而不是可选项。这是少数“单纯为了空间优化而优化”变得有实际价值的场景。条件允许的话还可以考虑分块计算——把矩阵横向切成若干块每块内用滚动数组处理块与块之间传递边界值这属于更进阶的操作比赛中偶尔能看到这种解法。6. 题目之外的实战建议这道题我前后给不少人讲过也在不同场合看着别人现场写过。一个观察是写得顺的人往往不是先想转移方程而是先把“递推依赖关系”画清楚——谁会走到当前格、当前格走到哪里一目了然。另一个建议是老生常谈但必须说别光看题解一定要动手写逐行注释版。你把每一行 dp 值的含义用中文写出来把自己在循环里每一步维护的“旧值”和“新值”都标注清楚才算真正掌握了。我建议朴素二维数组版、双数组滚动版、单数组原地覆盖版三种写法都各写一遍体会它们之间的差异和联系。这三版代码是面试时展示你“由浅入深”思考过程的绝佳素材。再写个我踩过的实用性坑LeetCode 上这道题的相似题很多平台全球化之后不同厂商的 OJ 对输入格式的解析方式有细微差别。有的平台会把输入作为原始字符串让你自行解析成二维数组有的已经给好了标准结构。这就意味着你写的核心函数要尽量解耦——保持“接收一个二维数组、返回一个整数”的干净接口这样解析逻辑再怎么变你的核心 DP 逻辑都不用改。最后强调一下语言选择的参考意义这道题不是只属于 Python 或 Java它在 C、Go、Rust 里都是很好的入门题。尤其是 Rust 的所有权机制会强迫你思考每个数组到底是借用还是拥有这对理解滚动数组的底层行为反而有助推作用。如果你有时间不妨用三种以上语言把这道题各写一遍体验会完全不同。这道题的代码量不大但信息密度很高——状态定义、边界处理、空间优化、数据覆盖顺序每一个点都能延伸出很多面试追问。我个人的体会是把这一题吃透胜过盲目刷十道同难度的题目。做减法比做加法更考验功力。 动态规划入门：LeetCode 931 下降路径最小和详解与空间优化
1. 题目拆解与动态规划思路的来源“下降路径最小和”这道题熟面孔了。LeetCode 第 931 题属于那种“必刷基础算法题”里的常青树尤其适合刚把动态规划提上日程的选手热身。它的原型问题其实是更经典的“最小路径和”LeetCode 64只不过把走法从“右 / 下”换成了“左下方 / 正下方 / 右下方”方向感一变很多人的状态定义思路就卡壳了。题目描述我先复述一下给定一个 n x n 的整数矩阵从第一行任意位置出发每次只能向下移动到下一行的相邻列即正下方、左下方、右下方走到最后一行时把路径经过的所有数字加起来要求这个和是最小的。注意几个关键字“第一行任意位置”、“每次只能向下走一行”、“可选的列偏移只有 -1、0、1”、“求最小和”。这几个关键字基本把解法锁死了——就是动态规划。为什么第一反应必须是 DP 而不是 DFS 或回溯因为每一步的选择都会影响后续所有走法暴力枚举所有路径是指数级的n 稍微给到 30 以上就废了。而它的决策结构又恰好满足“重叠子问题”和“最优子结构”从顶部走到 (i, j) 这个格子的最小和只与能从哪个格子走下来有关走到那个格子的最小和又只与其上方几格有关。层层递推最终答案肯定藏在“走到最后一行时所有格子的最小路径和”里取最小值。状态定义其实有两套思路。一种是从上往下推dp[i][j] 表示“从第一行任意位置出发到达第 i 行第 j 列时路径上数字和的最小值”。另一种是从下往上推dp[i][j] 表示“从第 i 行第 j 列出发走到最后一行的最小路径和”。这两种定义代码写出来大同小异但思路的出发点完全不同。我推荐从上往下推因为它的边界初始化更直观——第一行的 dp 值就直接等于矩阵第一行的值然后从第二行开始递推。转移方程长这样dp[i][j] matrix[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j1])其中只有 j 越界的那两个方向需要特殊处理。这方程本质上是在说你想到达 (i, j) 这一格合法前驱只可能是上一行的 j-1、j、j1 三个位置选它们之中走过来的最小路径和再把自己这一格的数字累加上去。生活化地理解就像你在爬一座金字塔形的阶梯每层只能从左、中、右三块立足点中挑一个落脚想知道踩到某一格子的最小体力消耗就看前一步选哪块砖最省劲。我见过有人在这道题上绕进另一个思路——把矩阵旋转 45 度当成三角形来做。原题太经典没必要这么折腾。老老实实开一个二维 dp 数组或者更进一步用一个一维数组滚动更新这道题的复杂度就能压到 O(n^2) 时间、O(n) 空间是面试官最乐意看到的形态。2. 三种主流语言实现与细节对比2.1 Python 版本用切片规避边界判断Python 写这种矩阵 DP 题代码量可以压得很薄。我先把最朴素的二维数组版本贴出来方便和后续一维优化做对比def minFallingPathSum(matrix): n len(matrix) if n 1: return matrix[0][0] # dp[j] 表示到达上一行第 j 列的最小路径和 dp matrix[0][:] for i in range(1, n): new_dp [0] * n for j in range(n): # 三个前驱中取最小注意 j0 和 jn-1 时边界 candidates [dp[k] for k in (j-1, j, j1) if 0 k n] new_dp[j] matrix[i][j] min(candidates) dp new_dp return min(dp)这个版本里有一个细节很多人初学时会漏掉dp matrix[0][:]必须带上切片符号[:]。如果直接写dp matrix[0]那么后续修改 dp 会直接改掉 matrix 的第一行虽然在当前这个算法流程里不至于引发致命错误但一旦你在同一个题解里同时维护多个变量很容易埋下数据污染的坑。切片复制是 Python 程序员的基本素养这里顺便养成就好。另外我用了一个列表推导式[dp[k] for k in (j-1, j, j1) if 0 k n]来优雅地过滤越界下标。这个写法在 Python 里很常用但是要强调一下性能问题每计算一个格子都要临时构造一个列表再取 min对于 n100 的规模完全无所谓但如果哪天刷到 n1000 以上的变体题这个列表推导式的开销会拖慢速度。那种极端情况下手动展开成 if-else 判断三个候选会更稳妥。那三行基础面试代码用这个解法已经够用了。我更喜欢 Python 版的原因在于它可以完全脱离显式边界判断把注意力集中在转移方程本身的逻辑上。这对初学者看代码时理解状态转移是有帮助的——不会被if j 0之类的分支打乱思路。2.2 Java 版本边界条件需要显式处理Java 没法像 Python 那样用切片优雅地过滤越界下标所以边界条件靠 if 判断来兜底。我建议写这种时候不要贪图代码简短按最直白的方式写反而容易对class Solution { public int minFallingPathSum(int[][] matrix) { int n matrix.length; if (n 1) { return matrix[0][0]; } 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[] newDp new int[n]; for (int j 0; j n; j) { int minPrev dp[j]; // 正上方 if (j 0) { minPrev Math.min(minPrev, dp[j - 1]); // 左上方 } if (j n - 1) { minPrev Math.min(minPrev, dp[j 1]); // 右上方 } newDp[j] matrix[i][j] minPrev; } dp newDp; } int ans Integer.MAX_VALUE; for (int val : dp) { ans Math.min(ans, val); } return ans; } }这里有一个容易写错的点是Math.min的嵌套顺序。有些初学者习惯先把三个候选都存入一个数组或者 list 里再遍历取最小值这在 Java 里不仅多此一举还会在n较大时产生不必要的对象分配。直接两两比较两次即可性能最好。另外if (n 1)这个特判不能删。矩阵只有一行时min(dp)也能返回正确结果但如果你在更复杂的变体题里忽略了这个边界后续访问matrix[i - 1]就可能数组越界。与其依赖后续逻辑偶然正确不如开局就把它堵死。Java 版的面试写法我还推荐在类名上直接用Solution这样在任何 OJ 平台上直接粘贴就能跑不用额外调整。有同行问我为什么不在主函数里加测试用例我的观点是刷算法题的核心是把核心逻辑写清楚评测逻辑留给平台跑本地调试时再去补 main 方法即可。2.3 C 版本注意数据溢出和内存布局C 版本的思路和 Java 完全一致但要注意一个语言本身的坑——矩阵里的元素范围是[-100, 100]n 最大到 100所以路径和的理论极限在-10000到10000之间用int完全够。但如果哪天题目改成元素范围更大或者 n 更大就要考虑用long long接收求和结果否则容易溢出。这是比赛里出题人最喜欢藏的陷阱。class Solution { public: int minFallingPathSum(vectorvectorint matrix) { int n matrix.size(); if (n 1) { return matrix[0][0]; } vectorint dp(matrix[0].begin(), matrix[0].end()); for (int i 1; i n; i) { vectorint newDp(n, 0); for (int j 0; j n; j) { int minPrev dp[j]; if (j 0) { minPrev min(minPrev, dp[j - 1]); } if (j n - 1) { minPrev min(minPrev, dp[j 1]); } newDp[j] matrix[i][j] minPrev; } dp.swap(newDp); } return *min_element(dp.begin(), dp.end()); } };用vectorint dp(matrix[0].begin(), matrix[0].end())做初始化比直接 matrix[0]更安全因为这相当于按值拷贝一行而不是共享底层数据。dp.swap(newDp)是 C 里常见的滚动数组替换方式它只交换两个 vector 的内部指针不涉及整块内存拷贝性能开销极低。最后求答案用的*min_element需要#include algorithm如果你是在 LeetCode 风格的环境下做题系统已经帮你引入了标准库不需要自己写头文件。但如果这个代码要移到本地编译就必须记得补上头文件。这种细节平时不显眼面试现场忘了写或者写错可能会给面试官留下基本功不扎实的印象。3. 空间优化与状态压缩思路3.1 为什么可以优化递推只依赖前一行很多算法题教程会直接告诉你“可以压缩到一维数组”但不说为什么。这道题里我们先看递推关系计算第 i 行的 dp 值只需要用到第 i-1 行的 dp 值再往上的行已经彻底用不到了。用流程图想一下就是逐层覆盖的节奏。类比来说你在记“走到每一格的当前最小和”时就像一个记账本每一页只记录上一层的读数。当你翻到新的一层时老的一层数据已经没有查询价值了直接擦掉重写就行。基于这个观察二维 dp 数组可以压缩成两个一维数组dp存上一行结果newDp存当前行结果。这是空间优化里最稳妥的“滚动数组”方案你永远不会读到被覆盖的旧值。上面三种语言的实现用的正是这种双一维数组方案从空间复杂度来讲已经从 O(n^2) 降到了 O(n)。3.2 只用一个数组的进阶玩法原地更新与覆盖顺序如果你想把空间压到极致可以用一个数组dp在遍历 j 的过程中直接原地更新。但这么做有一个非常关键的坑计算dp[j]时需要读到dp[j-1]的旧值上一行的值如果 j 从左往右遍历dp[j-1]已经被更新成当前行的新值了那就坏了。所以原地更新必须额外用一个变量暂存“即将被覆盖的旧值”类似滚动数组里常见的temp保存操作。伪代码大概是for i in range(1, n): temp dp[0] # 保存上一行 j0 的旧值 dp[0] matrix[i][0] min(dp[0], dp[1]) for j in range(1, n): # 此时 temp 保存的是上一行 j-1 的旧值dp[j] 还没被覆盖是上一行的旧值 # dp[j1] 也还是上一行的旧值 old dp[j] # 保存当前 dp[j] 的旧值供下一轮 j1 使用 dp[j] matrix[i][j] min(temp, dp[j], dp[j1] if j 1 n else large) temp old这段代码虽然行数多、心累但省下的那一个数组在绝大多数真实的 OJ 环境中已经没有明显价值了——毕竟 n 撑死 100。我个人的建议是面试时写两个数组的版本既清晰又不容易出错把“我能理解一数组原地更新的覆盖顺序”作为口头补充回答即可。真手写出 bug 了得不偿失。3.3 复杂度对比从 O(n^2) 空间到 O(1) 空间这里顺带把三种空间方案的对比整理一下方便你理解为什么优化是值得的方案空间复杂度优点缺点完整二维 dp 数组O(n^2)每个格子的路径和均可回溯占内存n 大时浪费两个一维数组滚动O(n)逻辑清晰、不易出错多一次数组拷贝可优化为交换单数组原地覆盖O(1)空间最省覆盖顺序处理复杂边界易错时间复杂度的底线是 O(n^2) 无论如何无法再降——因为你至少要遍历矩阵里每个格子一次。这个下界很多人会忽略面试时如果被问“还能不能更快”你可以理直气壮地说不能因为输入本身就有 n^2 个数据要处理。还有一个值得说明的点Java 和 C 里两个数组滚动时newDp每次 new 一个长度为 n 的数组对于 n100 来说毫无压力。但如果你把这道题的变体扩展到 n10^5矩阵从方形变成超宽那每一行都 new 新数组的开销就会比较明显此时应该考虑在循环外预先分配两块数组然后用swap交替使用避免频繁申请内存。4. 常见问题与排查技巧实录4.1 问题一边界下标导致数组越界这是我收到提问最多的问题尤其是第一次写 Java 和 C 版本的同学。每次循环里dp[j-1]在 j0 时直接变成dp[-1]直接抛ArrayIndexOutOfBoundsException或触发未定义行为。Python 虽然不会立刻报错但dp[-1]会取到数组最后一个元素结果就变成了“用下一行的值来算当前行”答案自然全错。排查技巧先把矩阵缩小到 2x2手动在纸上把每一次循环的 j、dp 值、newDp 值都推算一遍。这种小规模手工推演比在代码里打日志更直观也更能训练你建立状态转移的直觉。真正理解了“j-1 和 j1 分别会在哪些位置越界”之后再回头看代码里的 if 条件就会觉得那是顺理成章的写法。4.2 问题二一维数组更新时读到了当前行的新值如果你尝试把双数组改写成单数组最常见的结果就是答案偏大或偏小且错误随机分布。原因在于更新dp[j]时右边的dp[j-1]可能已经是当前行的新值破坏了“只能依赖上一行”的前提。这不是算法思路错误而是数据更新顺序导致的逻辑污染。我建议在调试这种错误时打印每一行更新后的 dp 数组和正确结果对比一下你会发现从某一行开始某一个格子的值出现诡异跳变。顺着这个格子的依赖链回溯很快就能定位是变量覆盖顺序的问题。4.3 问题二点五初始化时误用 0 或 Integer.MIN_VALUE矩阵里的数字可能全是负数此时用 0 作为 dp 初始值会导致任何负数的真实路径和都被错误地忽略。典型的错误是dp [0] * n如果第一行就有负数这个初始化会让后续所有正数路径的计算产生错误的最小值判断。标准做法是第一行直接用matrix[0]初始化 dp不需要额外填充极值。或者在更通用的模板里用一个大数比如10**9或Integer.MAX_VALUE / 2填充 dp再单独处理第一行。这里要注意用MAX_VALUE / 2而不是MAX_VALUE因为后面有 matrix[i][j]直接用MAX_VALUE可能会溢出变成负数反倒干扰取最小值。4.4 问题三只有一行或一列的特殊输入n1 时循环从 i1 开始就不会执行最后min(dp)其实就是dp[0]即matrix[0][0]——所以即使不特判结果也对。但如果是“只有一列”的矩阵呢题目会强调是 n x n所以一列的情况不存在。但很多变体题会改成 m x n 矩形此时若 n1转移时就不能取j1和j-1需要特判。我的建议是模板里把n 1提前返回这不仅是为了正确性更是提醒你自己这道题的最简输入形态是什么。4.5 问题四误以为必须从 (0,0) 出发答案只查 dp[n-1][n-1]这道题和“最小路径和”最大的区别就是起点和终点不固定。起点可以是第一行任意列终点可以是最后一行任意列。很多人把 64 题的代码改一改就套过来算出的却是从左上角到右下角的最小路径和答案自然不对。正确做法的收尾是取min(dp)最后一行的所有值中的最小值而不是dp[n-1]。面试时这个小小的差异就是区分“背模板”和“理解题意”的关键信号。我建议在写完代码后自己在注释里写清楚这个题解的终点不固定所以答案在最后一行取 min不要默认最后一行的最后一个元素。4.6 问题五原地修改 matrix 的偏好有人为了省一个数组直接在 matrix 上累加 dp 值。这个思路理论上没问题——因为第 i 行只会被读一次第 i 行的原始值之后不再需要了。但我不推荐这么写。原因一修改输入数据不是好习惯万一之后面试官追加问你“如何打印出最小路径的完整轨迹”你就无法依赖原始矩阵了原因二在 Debug 时保留原始矩阵能帮你随时核对每一步计算结果。清晰的代码永远比省一点内存更重要。4.7 排查思路速查表症状可能原因排查顺序j 从 0 开始却报数组越界踩到 dp[j-1] 或 matrix[i][j-1]检查 j 是否等于 0结果偏大初始值设成了 0 或正数忽略了负数路径检查 dp 初始化方式结果偏小且逐行漂移单数组覆盖顺序错误打印每轮 dp 对比只在 n1 时报错没有处理单行矩阵的边界入口直接加特判答案明显错但递推没问题终点取错了位置确认收尾取 min(dp)5. 变体与延伸从这道题拓展到一类问题5.1 变体一三角形最小路径和LeetCode 120 题“三角形最小路径和”是这道题最出名的同门兄弟。它把矩形换成了阶梯形排列转移方程从min(dp[i-1][j-1], dp[i-1][j])变成了只有左和右两个方向。思路、代码、优化手段几乎完全一致。刷完下降路径最小和接着刷 120连续两道题下来你对“走格子的 DP”基本就有肌肉记忆了。5.2 变体二矩形网格的上下左右四方向移动如果题目改成“允许左右移动并可以向上”那就变成了更复杂的图论最短路问题需要用 Dijkstra 或 BFS 来解DP 的简单递推已经失效。这个区分非常重要——写题前先看限制条件移动方向是单向还是双向是只能向下还是可以回头决定了整个解法的类别。我见过很多人把题目稍一变形就强行套 DP结果越套越乱。正确的方法论是先分析递推依赖的方向性如果状态之间只有单向依赖且无环DP 才成立一旦可能出现循环依赖就得换算法。5.3 变体三要求输出路径本身而不只是最小值原题只要最小和但面试官经常会追加一句——“你能不能把那条路径给我打印出来”这时就需要额外开一个 parent 数组在更新 dp 的同时记录每个格子是从哪个前驱走来的最后从最后一行最小值对应的格子回溯到第一行。这个技巧虽然简单但如果没有在写第一版代码时就预留后续重构会比较痛苦。我建议在平时练习时就做好习惯dp 初始化和转移时顺手在另一个数组里记录“上一行选择的列”。虽然原题没要求但这个扩展在小厂面试里出现的频率不低。把基础逻辑写扎实追加深挖时你才有余裕。5.4 变体四大规模矩阵下的内存优化当 n 到达 1000 或者更大时O(n^2) 的空间可能触碰内存限制。此时单数组原地覆盖就是迫不得已的选择而不是可选项。这是少数“单纯为了空间优化而优化”变得有实际价值的场景。条件允许的话还可以考虑分块计算——把矩阵横向切成若干块每块内用滚动数组处理块与块之间传递边界值这属于更进阶的操作比赛中偶尔能看到这种解法。6. 题目之外的实战建议这道题我前后给不少人讲过也在不同场合看着别人现场写过。一个观察是写得顺的人往往不是先想转移方程而是先把“递推依赖关系”画清楚——谁会走到当前格、当前格走到哪里一目了然。另一个建议是老生常谈但必须说别光看题解一定要动手写逐行注释版。你把每一行 dp 值的含义用中文写出来把自己在循环里每一步维护的“旧值”和“新值”都标注清楚才算真正掌握了。我建议朴素二维数组版、双数组滚动版、单数组原地覆盖版三种写法都各写一遍体会它们之间的差异和联系。这三版代码是面试时展示你“由浅入深”思考过程的绝佳素材。再写个我踩过的实用性坑LeetCode 上这道题的相似题很多平台全球化之后不同厂商的 OJ 对输入格式的解析方式有细微差别。有的平台会把输入作为原始字符串让你自行解析成二维数组有的已经给好了标准结构。这就意味着你写的核心函数要尽量解耦——保持“接收一个二维数组、返回一个整数”的干净接口这样解析逻辑再怎么变你的核心 DP 逻辑都不用改。最后强调一下语言选择的参考意义这道题不是只属于 Python 或 Java它在 C、Go、Rust 里都是很好的入门题。尤其是 Rust 的所有权机制会强迫你思考每个数组到底是借用还是拥有这对理解滚动数组的底层行为反而有助推作用。如果你有时间不妨用三种以上语言把这道题各写一遍体验会完全不同。这道题的代码量不大但信息密度很高——状态定义、边界处理、空间优化、数据覆盖顺序每一个点都能延伸出很多面试追问。我个人的体会是把这一题吃透胜过盲目刷十道同难度的题目。做减法比做加法更考验功力。