数据结构与算法 / 系统课时
计算带权网格的最小路径和
计算带权网格的最小路径和
当每个网格位置具有不同代价时,状态不再记录“有多少条路”,而要记录“到这里最少花多少代价”。核心转移仍来自上方和左方,但聚合操作从加总方案数变成选择更小的前驱代价,并且要明确表示不可达状态。
学习目标
- 将路径计数状态改造成最小代价状态并写出转移式
- 使用无穷大哨兵统一处理边界和不可达位置
- 判断遍历顺序、状态含义与最终答案是否一致
把状态改成最小代价
设 weight[i][j] 是进入格子 (i, j) 需要支付的代价,只允许向右或向下移动。定义 dp[i][j] 为从起点到当前位置,并且包含当前位置权重的最小路径和。
当前位置若可到达,最后一步仍然只能来自上方或左方,因此有:
与路径计数相比,状态依赖关系没有改变,改变的是组合规则。计数题将两个来源相加;最小代价题从来源中选择更优者,再叠加当前位置的成本。

用无穷大表示没有合法来源
如果直接把不存在的前驱写成 0,最小值运算会错误地偏向这个不存在的方向。例如首行格子没有上方来源,若把上方代价当成 0,算法就会认为可以从网格外免费进入。
更稳妥的方法是用正无穷 float('inf') 表示“当前没有可行路径”。这样只要另一侧存在有限代价,min 就会自动选择合法来源;若两侧都是无穷,则当前位置也保持不可达。
障碍物同样可以设为无穷。这样边界与障碍都统一成“不可作为最优前驱”的状态,不必为每种情况重写转移逻辑。
完成最小路径计算
下面的示例用 None 表示不可进入的格子。起点代价直接等于自身权重,其余位置从上方和左方的较小累计代价转移。
def min_path_sum(weight):
rows = len(weight)
cols = len(weight[0])
inf = float('inf')
if weight[0][0] is None or weight[-1][-1] is None:
return None
dp = [[inf] * cols for _ in range(rows)]
dp[0][0] = weight[0][0]
for i in range(rows):
for j in range(cols):
if weight[i][j] is None or (i == 0 and j == 0):
continue
top = dp[i - 1][j] if i > 0 else inf
left = dp[i][j - 1] if j > 0 else inf
best = min(top, left)
if best != inf:
dp[i][j] = best + weight[i][j]
return None if dp[-1][-1] == inf else dp[-1][-1]
weight = [
[1, 3, 1, 2],
[2, None, 1, 5],
[4, 2, 1, 1],
]
print(min_path_sum(weight))预期输出
7一条达到最小代价的路线会累计得到 7。程序只保存最小代价值,因此能够求出答案,但不会自动保存完整路径;若还需要还原经过哪些格子,应额外记录每个状态选择的前驱。
最优来源与遍历顺序
这里仍然按从上到下、从左到右扫描,因为 dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]。如果题目允许四个方向自由移动,当前格子可能反过来依赖尚未确定的右侧或下方状态,此时一次二维扫描通常不再成立,需要判断问题是否应改用图上的最短路径算法。
本题处理每个格子一次,时间复杂度为 O(mn),二维状态空间为 O(mn)。若只要求最小路径和而不还原路线,也可以把状态压缩成一维数组,使空间降为 O(n)。无穷大哨兵的价值不仅是方便写边界,它还把“不可达”纳入了同一套最小值转移规则,使障碍、断路和普通位置可以共享一套状态模型。