网格中的最小路径代价

记牢这套转移:每一格的最小代价,等于自己的格值,加上「从上一行所有来路里挑一条最省的」。下面就照着这句,从第 0 行开始一格一格填。

先看网格 · 每格的原始值：这是舞台上的动态规划表,一开始每个格子先写上它在 grid 里的原始值:第 0 行是 5 和 3,第 1 行是 4 和 0,第 2 行是 2 和 1。接下来从第 1 行起,我们会把每格改写成「到达这格的最小总代价」,格值本身则并进代价里。第 0 行没有移动,它的代价就等于格值,可以直接定下来。

第 0 行基线 · 列 0 的 f = 5：先填第 0 行,它是所有路径的起点。因为从第一行出发本身不产生移动代价,所以到第 0 行每一格的最小代价,就等于它自己的格值。列 0 这格值是 5,f 就记 5,标成绿色确定下来。

第 0 行基线 · 列 1 的 f = 3：同理,第 0 行列 1 这格值是 3,到它的最小代价就是 3。第 0 行两格都定了,f 这一行是 [5, 3]。这一行是后面所有计算的地基,往下每一格都要回头看它。

读表规则 · 移动代价按「出发格的值」查行：往下走之前,先把 moveCost 怎么查说清楚。它有 m 乘 n 行,行号从 0 到 m 乘 n 减 1,查表用的是「出发那格里的数值 v」当行号,不是坐标。比如上一行列 0 的值是 5,要落到本行列 0,查的就是 moveCost 第 5 行第 0 列。这个「按值查行」是本题最容易记错的地方,盯住它。

算 (1,0) · 试来路:上一行 列 0：现在算格子 (1,0),它的值是 4。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 5,它的格值是 5,要落到本行列 0,查 moveCost 第 5 行第 0 列得移动代价 14。三样加起来:5 加 14 加 4 等于 23。

算 (1,0) · 试来路:上一行 列 1：再试另一条来路:从上一行 列 1 过来。那格 f 是 3,格值 3,移到本列的代价查表得 18。合计 3 加 18 加 4 等于 25。和上一条 23 摆一起比,谁小取谁。

算 (1,0) · 落值 23：两条来路的代价是 23 和 25,取更小的 23。所以到 (1,0) 的最小总代价就是 23,它是从上一行 列 0 接过来的。把这格填成 23,标绿确定。

算 (1,1) · 试来路:上一行 列 0：现在算格子 (1,1),它的值是 0。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 5,它的格值是 5,要落到本行列 1,查 moveCost 第 5 行第 1 列得移动代价 3。三样加起来:5 加 3 加 0 等于 8。

算 (1,1) · 试来路:上一行 列 1：再试另一条来路:从上一行 列 1 过来。那格 f 是 3,格值 3,移到本列的代价查表得 6。合计 3 加 6 加 0 等于 9。和上一条 8 摆一起比,谁小取谁。

算 (1,1) · 落值 8：两条来路的代价是 8 和 9,取更小的 8。所以到 (1,1) 的最小总代价就是 8,它是从上一行 列 0 接过来的。把这格填成 8,标绿确定。

第 1 行填完 · f = [23, 8]：第 1 行两格都算完了,f 变成 [23, 8]。注意此刻格子里显示的已经不是原始格值,而是「到这格的最小总代价」。第 2 行往上看的就是这两个数;原始格值 4 和 0 只在查移动代价时还用得上。

算 (2,0) · 试来路:上一行 列 0：现在算格子 (2,0),它的值是 2。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 23,它的格值是 4,要落到本行列 0,查 moveCost 第 4 行第 0 列得移动代价 2。三样加起来:23 加 2 加 2 等于 27。

算 (2,0) · 试来路:上一行 列 1：再试另一条来路:从上一行 列 1 过来。那格 f 是 8,格值 0,移到本列的代价查表得 9。合计 8 加 9 加 2 等于 19。和上一条 27 摆一起比,谁小取谁。

算 (2,0) · 落值 19：两条来路的代价是 27 和 19,取更小的 19。所以到 (2,0) 的最小总代价就是 19,它是从上一行 列 1 接过来的。把这格填成 19,标绿确定。

算 (2,1) · 试来路:上一行 列 0：现在算格子 (2,1),它的值是 1。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 23,它的格值是 4,要落到本行列 1,查 moveCost 第 4 行第 1 列得移动代价 4。三样加起来:23 加 4 加 1 等于 28。

算 (2,1) · 试来路:上一行 列 1：再试另一条来路:从上一行 列 1 过来。那格 f 是 8,格值 0,移到本列的代价查表得 8。合计 8 加 8 加 1 等于 17。和上一条 28 摆一起比,谁小取谁。

算 (2,1) · 落值 17：两条来路的代价是 28 和 17,取更小的 17。所以到 (2,1) 的最小总代价就是 17,它是从上一行 列 1 接过来的。把这格填成 17,标绿确定。

第 2 行填完 · f = [19, 17]：最后一行也填完了,f 是 [19, 17]。这两个数分别是「走到最后一行列 0」和「走到最后一行列 1」的最小总代价。因为终点可以是最后一行任意一列,答案就在这两个里挑小的,下一帧收束。

最后一行取最小 · 答案 = 17：整张表填满了。最后一行的 f 是 [19, 17],因为终点可以是最后一行的任意一列,取里面最小的那个就是答案。17 比 19 小,所以最小总代价是 17,落在列 1。

回溯 · 从答案格往上找来路：答案定在最后一行列 1 那个 17。顺着填表时记下的「从哪来」往回倒:这格是从第 1 行列 1 接来的;第 1 行列 1 这格现在显示的是 DP 代价 8,它的原始格值是 0,这个 8 又是从第 0 行列 0 的 5 接来的。这样一路往上,就把最省的那条路摸出来了。

完整路径 · 5 到 0 到 1,总计 17：整条最优路径亮出来:第 0 行列 0 的 5,到第 1 行列 1 的 0,再到第 2 行列 1 的 1。三个格值 5 加 0 加 1 等于 6;第一步从值 5 移到列 1 代价 3,第二步从值 0 移到列 1 代价 8,两步合 11。6 加 11,正好是 17。和开头说的路径对上了。

边界想清:多行时逐行滚动、两行时只一次移动、终点在末行任意列取最小。

面试重点:状态 f[i][j]、按行滚动转移、移动代价按值查行、末行取最小、空间可压到 O(n)。