Kimi LeetCode 3651. 带传送的最小路径成本 Python3实现
这是 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 代码
```python
from typing import List
class 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 = 0
for 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[j+1] 表示当前行处理到第 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 # 起点成本为 0
for i in range(m):
for j in range(n):
x = grid[i][j]
# 方案1：从左边或上边走过来
standard_move = min(new_f[j], new_f[j + 1]) + x
if 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:
break
suf_min_f = new_suf
return 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[j+1]` 分别代表从左边和上边转移过来的状态，空间复杂度从 `O(mn)` 降到 `O(n)`
- 提前终止：如果某一轮的后缀最小值数组不再变化，说明增加传送次数已经无法优化结果，可以直接退出循环
参考来源：