数据结构与算法 / 系统课时

计算带权网格的最小路径和

计算带权网格的最小路径和

当每个网格位置具有不同代价时,状态不再记录“有多少条路”,而要记录“到这里最少花多少代价”。核心转移仍来自上方和左方,但聚合操作从加总方案数变成选择更小的前驱代价,并且要明确表示不可达状态。

学习目标

  • 将路径计数状态改造成最小代价状态并写出转移式
  • 使用无穷大哨兵统一处理边界和不可达位置
  • 判断遍历顺序、状态含义与最终答案是否一致

把状态改成最小代价

设 weight[i][j] 是进入格子 (i, j) 需要支付的代价,只允许向右或向下移动。定义 dp[i][j] 为从起点到当前位置,并且包含当前位置权重的最小路径和。

当前位置若可到达,最后一步仍然只能来自上方或左方,因此有:

dp[i][j]=weight[i][j]+min⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = weight[i][j] + \min(dp[i-1][j], dp[i][j-1])

与路径计数相比,状态依赖关系没有改变,改变的是组合规则。计数题将两个来源相加;最小代价题从来源中选择更优者,再叠加当前位置的成本。

带权网格最小路径状态转移

用无穷大表示没有合法来源

如果直接把不存在的前驱写成 0,最小值运算会错误地偏向这个不存在的方向。例如首行格子没有上方来源,若把上方代价当成 0,算法就会认为可以从网格外免费进入。

更稳妥的方法是用正无穷 float('inf') 表示“当前没有可行路径”。这样只要另一侧存在有限代价,min 就会自动选择合法来源;若两侧都是无穷,则当前位置也保持不可达。

障碍物同样可以设为无穷。这样边界与障碍都统一成“不可作为最优前驱”的状态,不必为每种情况重写转移逻辑。

完成最小路径计算

下面的示例用 None 表示不可进入的格子。起点代价直接等于自身权重,其余位置从上方和左方的较小累计代价转移。

python
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))

预期输出

text
7

一条达到最小代价的路线会累计得到 7。程序只保存最小代价值,因此能够求出答案,但不会自动保存完整路径;若还需要还原经过哪些格子,应额外记录每个状态选择的前驱。

最优来源与遍历顺序

这里仍然按从上到下、从左到右扫描,因为 dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]。如果题目允许四个方向自由移动,当前格子可能反过来依赖尚未确定的右侧或下方状态,此时一次二维扫描通常不再成立,需要判断问题是否应改用图上的最短路径算法。

本题处理每个格子一次,时间复杂度为 O(mn),二维状态空间为 O(mn)。若只要求最小路径和而不还原路线,也可以把状态压缩成一维数组,使空间降为 O(n)。无穷大哨兵的价值不仅是方便写边界,它还把“不可达”纳入了同一套最小值转移规则,使障碍、断路和普通位置可以共享一套状态模型。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

计算带权网格的最小路径和

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通