题目描述
思路解析
一句话答案：LeetCode 2304 网格中的最小路径代价：从第一行走到最后一行，靠逐行滚动的动态规划，每格取上一行所有来路里最省的一条、加本格值与移动代价，末行取最小，时间 O(m·n²)。
从第一行走到最后一行，最小总代价怎么算
给一张 m 行 n 列的网格 grid，格子是互不相同的整数。从第一行出发，每步落到下一行任意一列，直到最后一行。总代价 = 沿途格值之和加每次跨行的移动代价；moveCost[v][j] 是从值 v 的格子落到下一行第 j 列的代价。题面例子 grid=[[5,3],[4,0],[2,1]]，最优路径 5 到 0 到 1，答案 17。
把每条路都枚举一遍，为什么行不通
直觉是枚举每条从头到尾的路比总代价。可每一行都能落到 n 列任意一个，m 行连乘是 n 的 (m−1) 次方条路，n 和 m 到 50 就跑不完。但走到某一格后，往下怎么走只跟站在这格、已花多少有关，所以不必记整条来路，只需记住走到每一格的最小代价。
逐行滚动，f[j] 记走到本行第 j 列的最省花费
设 f[j] 为从第一行走到本行第 j 列的最小总代价。第 0 行是起点、出发不付移动代价，f 就是格值。往下逐行推：算本行第 j 列的 f，枚举上一行每列 k 当来路，候选 = f[k] 加移到本列 j 的代价加本格值 grid[i][j]，取最小。
移动代价用出发格的数值查 moveCost 的行、不是坐标：上一行第 k 列的值是 grid[i−1][k]，就查 moveCost[grid[i−1][k]][j]。推下一行只用得到紧挨的上一行，只留它逐行推进，这就是滚动数组省空间的办法。
一行填满再填下一行，末行取最小收口
逐行往下填，第 0 行是格值，本行 f 算好后成为下一行的地基，一路压到最后一行。终点没指定落在哪列，末行每列的 f 是走到那列的最小代价，扫一遍取最小即答案。
拿 [[5,3],[4,0],[2,1]] 把每格逐步填一遍
moveCost=[[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]。第 0 行抄格值 f=[5, 3]。
第 1 行取两来路较小者。(1,0)：5 加 moveCost[5][0]=14 加 4 得 23，或 3 加 18 加 4 得 25，取 23。(1,1)：5 加 moveCost[5][1]=3 加 0 得 8，或 3 加 6 加 0 得 9，取 8。f=[23, 8]。
第 2 行（上一行 f=[23, 8]、格值 4 和 0）。(2,0)：23 加 moveCost[4][0]=2 加 2 得 27，或 8 加 moveCost[0][0]=9 加 2 得 19，取 19。(2,1)：23 加 4 加 1 得 28，或 8 加 moveCost[0][1]=8 加 1 得 17，取 17。末行 f=[19, 17]，最小 17 即答案。
复杂度，再逐个点名填表最常写反的四处
时间 O(m·n²)：m 行、每行 n 列、每列再枚举 n 条来路，三层嵌套。空间 O(n)，滚动数组只留上一行和本行两份，不存整张 m 乘 n 的表。
写反的四处：moveCost 按数值查行，当坐标查会查错行；本格值 grid[i][j] 要计入总代价，漏了偏小；来路是上一行任意一列而非正上方，少枚举会错过更省解；答案取末行 f 最小值，取第 0 列会漏掉更优解。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套转移:每一格的最小代价,等于自己的格值,加上「从上一行所有来路里挑一条最省的」。下面就照着这句,从第 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)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = grid[0] for i in range(1, m): g = [inf] * n for j in range(n): for k in range(n): g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]) f = g return min(f)复杂度
- 时间：O(m·n²)，m 行,每行 n 个目标列,每个目标列又要枚举上一行的 n 个来路列,三层嵌套。行数 m 乘上每行 n 乘 n 的转移,总量随 m 乘 n 的平方增长
- 空间：O(n)，按峰值算。滚动数组只保留上一行的 f 和当前行的 g,各长 n;不需要存整张 m 乘 n 的表。若为回溯路径而保留全表则是 O(m·n),本解只求最小值故 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的状态和转移怎么设计?
追问复杂度是多少,能优化吗?
追问为什么最后要在整行里取最小?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格图中鱼的最大数目
LeetCode 2658 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题