这是 LeetCode 3651「带传送的最小路径成本」的 Python3 实现。题目概述给定一个 m × n 的网格 grid每个格子有一个成本值。从左上角 (0,0) 出发目标是到达右下角 (m-1,n-1)。移动规则- 普通移动只能向右或向下移动花费为目标格子的成本值- 传送最多使用 k 次。可以从任意格子传送到另一个值不大于当前格子值的格子传送花费为 0解题思路核心思想是分层 DP按使用传送次数 0, 1, ..., k 逐层计算最小成本。1. 普通 DP无传送dp[i][j] 表示从 (0,0) 走到 (i,j) 的最小成本只能向右或向下2. 传送优化使用传送后可以从之前任意一个值 ≥ 当前格子值的格子免费跳过来。为了快速查询维护一个后缀最小值数组 suf_min_f[v]表示所有值 ≥ v 的格子中使用当前次数传送后的最小成本3. 逐层迭代每多一次传送机会重新计算一遍整个网格的 DP同时利用上一层的后缀最小值来优化传送决策Python3 代码pythonfrom typing import Listclass Solution:def minCost(self, grid: List[List[int]], k: int) - int:m, n len(grid), len(grid[0])# 特判如果可以直接传送到终点if k 0 and grid[0][0] grid[m - 1][n - 1]:return 0# 找到网格中的最大值用于后缀最小值数组mx 0for row in grid:mx max(mx, max(row))INF float(inf)# suf_min_f[v] 表示所有值 v 的格子中使用 t-1 次传送的最小成本suf_min_f [INF] * (mx 2)# f[j1] 表示当前行处理到第 j 列时的最小成本滚动数组优化f [INF] * (n 1)for t in range(k 1):min_f [INF] * (mx 1) # min_f[v] 记录当前层中值为 v 的格子的最小成本new_f [INF] * (n 1)if t 0:new_f[1] 0 # 起点成本为 0for i in range(m):for j in range(n):x grid[i][j]# 方案1从左边或上边走过来standard_move min(new_f[j], new_f[j 1]) xif i 0 and j 0 and t 0:standard_move 0# 方案2从之前某个值 x 的格子传送过来花费为0# suf_min_f[x] 已经包含了所有可用传送来源的最小成本new_f[j 1] min(standard_move, suf_min_f[x])# 更新当前层中值为 x 的格子的最小成本min_f[x] min(min_f[x], new_f[j 1])f new_f# 为下一层准备后缀最小值数组# new_suf[v] min(所有值 v 的格子的最小成本)new_suf [INF] * (mx 2)for v in range(mx, -1, -1):new_suf[v] min(new_suf[v 1], min_f[v])# 如果后缀最小值不再变化提前结束if suf_min_f new_suf:breaksuf_min_f new_sufreturn f[n]复杂度分析- 时间复杂度O(k × m × n k × V)其中 V 是网格中的最大值。主要开销是 k 轮 DP 遍历网格以及每轮构建后缀最小值数组- 空间复杂度O(m × n) 可以优化到 O(n V)使用滚动数组 new_f 仅需维护一行的 DP 值加上后缀最小值数组 O(V)关键点- 后缀最小值优化suf_min_f[x] 表示从任意一个值 ≥ x 的格子传送过来的最小成本这样传送决策从 O(mn) 降到了 O(1)- 滚动数组new_f[j] 和 new_f[j1] 分别代表从左边和上边转移过来的状态空间复杂度从 O(mn) 降到 O(n)- 提前终止如果某一轮的后缀最小值数组不再变化说明增加传送次数已经无法优化结果可以直接退出循环参考来源