下降路径最小和

先别急着写代码，想想到底有多少条路。

最直接的想法：把每条可能的下降路都走一遍，算出和，取最小。逻辑没错，但慢。每往下一行最多分叉 ×3，路径数接近 3ⁿ，根因是同一个格子被无数条路反复经过、反复重算。

要落到格子 (i,j)，上一步只可能站在它正上方 (i-1,j)、左上 (i-1,j-1) 或右上 (i-1,j+1) 这三格之一。所以「到 (i,j) 的最小和」= 这三格里最小的那个，再加上 (i,j) 自己。

与其重复枚举每条路，不如把每个格子的最小代价记进一张表。递推式：dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。「到 (i,j) 的所有路」按最后一步从哪格下来，不重不漏分成三类，三格早算好了——直接查表取最小，绝不重算。

建表 · 行0 = 起点：建一张和矩阵一样大的 4×4 表，dp[i][j] 存「落到这格的最小路径和」。第一行就是起点，没有上一步，所以 dp[0][j] 直接等于 matrix[0][j]：2, 1, 3, 4。下面一格一格往下填。

看 dp[1][0] 的来源：先填行1。第0格在最左边，没有左上那一格，只能从正上(2)或右上(1)落下来。先把这两个来源高亮出来，看清能从哪里走过来。

填 dp[1][0]：正上 2、右上 1，取最小 1，加上自己 matrix=6 → dp[1][0] = 7。左边界要小心：少看一个方向。

看 dp[1][1] 的来源：第1格在中间，上方三格全有：左上2、正上1、右上3。先把三个来源高亮出来——这就是「三选一取最小」的标准情形。

填 dp[1][1]：三个来源里最小是正上的 1，加自己 5 = 6。

填 dp[1][2]：第2格也在中间，左上1、正上3、右上4，最小是左上的 1，加自己 4 = 5。

填 dp[1][3]：第3格在最右边，没有右上，只能从左上(3)或正上(4)落下来。取最小 3，加自己 2 = 5。行1 填完：[7, 6, 5, 5]。右边界同样要少看一个方向。

注意：填行2时，我们只关心行1的 dp 值 7/6/5/5，完全不用管它们是怎么来的。这就是 DP 省时间的根本——上一行的最优结果被缓存住了。

看 dp[2][0] 的来源：开始填行2。第0格在最左边，没有左上，来源只有正上(7)和右上(6)，先把这两个来源高亮。

填 dp[2][0]：正上7、右上6，取最小 6，加自己 matrix=7 = 13。

填 dp[2][1]：填行2第1格 matrix=8。上方三格 7/6/5 都有，最小是右上的 5，加自己 8 = 13。

填 dp[2][2]：填行2第2格 matrix=1。上方三格 6/5/5，最小 5，加自己 1 = 6。这个很小的 6 待会儿是最优路上的关键一站。

填 dp[2][3]：填行2第3格 matrix=9。最右边没有右上，从左上(5)或正上(5)落下，取最小 5，加自己 9 = 14。行2 填完：[13, 13, 6, 14]。

填 dp[3][0]：填最后一行第0格 matrix=5。最左边没有左上，从正上(13)或右上(13)落下，取最小 13，加自己 5 = 18。

看 dp[3][1] 的来源：填行3第1格前，先看它的上方三格：左上13、正上13、右上只有 6。一眼就知道该斜接到那个小 6 上。

填 dp[3][1]：最小是右上的 6，加自己 matrix=2 = 8。它没走两个 13，而是斜接到那个小 6 上，这就是 DP 自动挑出的便宜路。

填 dp[3][2]：填最后一行第2格 matrix=3。上方三格 13/6/14，最小是正上的 6，加自己 3 = 9。

填 dp[3][3]：填最后一行第3格 matrix=8。最右边没有右上，从左上(6)或正上(14)落下，取最小 6，加自己 8 = 14。最后一行填完：[18, 8, 9, 14]。

取最后一行最小：下降路径可以停在最后一行任意一格，所以答案是最后一行 dp 值里最小的那个：min(18,8,9,14) = 8，落在列1。别只盯某一列。

回溯最优路径：从末行最小处 dp[3][1]=8 反向回溯：它从右上 6 来 → 6 是 dp[2][2] 从正上 5 来 → 5 是 dp[1][2] 从左上 1 来 → 1 是 dp[0][1]。对应原矩阵 1 → 4 → 1 → 2，正好加起来 8。

每个格子只算一次、每次只看上方三格，总共 n² 次小计算就出答案，比指数级暴力快出几个数量级。

不同路径那题求「有几条路」，要把上、左两格的方案数加起来；本题求「最小代价」，要在上方三格里挑一个最便宜的接上来。看清是「计数」还是「最优」，递推式就不会写反。

三角形最小路径和、不同路径 II、最小路径和，骨架都是这一套：定义 dp[i][j]，找清楚它能从哪几格转移过来，取最优。

雷区实演 · 最左列若误读左上：填最左列 (i,0) 时，左上是 (i-1,-1)，根本不存在。不加 j>0 判断，Python 会取到上一行末尾的错值、C++/Java 直接越界崩。所以边界判断不是可有可无。

边界三连：先想最小规模(1×1)、含负数(取最小照样成立)、小网格(2×2 手算验证)。负数不影响逻辑，因为我们一路取的是最小。

面试追问：把「依赖上一行 → 可滚动数组 → O(n) 空间」讲清楚，是这题面试的加分点。