T3651.带传送的最小路径成本

dp, https://leetcode.cn/problems/minimum-cost-path-with-teleportations/

给你一个 m x n 的二维整数数组 grid 和一个整数 k。你从左上角的单元格 (0, 0) 出发，目标是到达右下角的单元格 (m - 1, n - 1)。

有两种移动方式可用：

普通移动：你可以从当前单元格 (i, j) 向右或向下移动，即移动到 (i, j + 1)（右）或 (i + 1, j)（下）。成本为目标单元格的值。
传送：你可以从任意单元格 (i, j) 传送到任意满足 grid[x][y] <= grid[i][j] 的单元格 (x, y)；此移动的成本为 0。你最多可以传送 k 次。

返回从 (0, 0) 到达单元格 (m - 1, n - 1) 的最小总成本。

示例 1:

输入: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2

输出: 7

解释:

我们最初在 (0, 0)，成本为 0。

当前位置	移动	新位置	总成本
`(0, 0)`	向下移动	`(1, 0)`	`0 + 2 = 2`
`(1, 0)`	向右移动	`(1, 1)`	`2 + 5 = 7`
`(1, 1)`	传送到 `(2, 2)`	`(2, 2)`	`7 + 0 = 7`

到达右下角单元格的最小成本是 7。

示例 2:

输入: grid = [[1,2],[2,3],[3,4]], k = 1

输出: 9

解释:

我们最初在 (0, 0)，成本为 0。

当前位置	移动	新位置	总成本
`(0, 0)`	向下移动	`(1, 0)`	`0 + 2 = 2`
`(1, 0)`	向右移动	`(1, 1)`	`2 + 3 = 5`
`(1, 1)`	向下移动	`(2, 1)`	`5 + 4 = 9`

到达右下角单元格的最小成本是 9。

提示:

2 <= m, n <= 80
m == grid.length
n == grid[i].length
0 <= grid[i][j] <= 10^4
0 <= k <= 10

这是一个动态规划问题，结合了网格路径搜索和一种基于数值大小的“零成本”传送机制。

核心思路

状态定义：令 dp[p][i][j] 表示使用最多 p 次传送到达单元格 (i, j) 的最小成本。由于普通移动只能向右或向下，且传送次数有限，我们可以按传送次数 $p$ 从 $0$ 到 $k$ 逐步计算。
普通移动（Normal Move）：对于固定的传送次数 $p$ ，在单元格 (i, j)：
- 可以从上方 (i-1, j) 移动过来，成本增加 grid[i][j]。
- 可以从左方 (i, j-1) 移动过来，成本增加 grid[i][j]。公式：dp[p][i][j] = min(dp[p][i][j], dp[p][i-1][j] + grid[i][j], dp[p][i][j-1] + grid[i][j])。
传送（Teleportation）：传送不消耗金钱，但消耗一次传送机会。规则：从任意 (i, j) 传送到 (x, y)，要求 grid[x][y] <= grid[i][j]。这意味着在进行第 $p + 1$ 次传送时，如果我们想传送到目标值 $V_{t a r g e t}$ 的单元格，我们需要在第 $p$ 次状态中已经到达过任意一个网格值 $V_{s o u r c e} \geq V_{t a r g e t}$ 的单元格。
- 为了高效计算，我们可以维护一个辅助数组 min_at_val[v]，记录在当前 $p$ 次传送下，所有 grid[i][j] >= v 的单元格中最小的 dp 值。
- dp[p+1][x][y] = min(dp[p][i][j]) 满足 grid[i][j] >= grid[x][y]。

算法步骤

初始化 dp 数组为无穷大，起点 dp[0][0] = 0。
遍历传送次数 $p$ 从 $0$ 到 $k$ ：
- 执行 普通移动更新：利用双层循环更新当前 $p$ 层的所有单元格成本。
- 记录当前层的终点 dp[m-1][n-1] 到最终答案。
- 如果 $p < k$ ，执行 传送预处理：
  - 统计当前层各网格值对应的最小成本。
  - 计算后缀最小值：min_at_val[v] 表示网格值 $\geq v$ 的所有单元格的最小成本。
  - 将这些最小成本作为第 $p + 1$ 层各单元格的初始值（即通过第 $p + 1$ 次传送到达该位置）。

代码实现

python

from typing import List

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        m = len(grid)
        n = len(grid[0])
        inf = float('inf')
        
        # dp[i][j] 表示在当前传送次数下到达 (i, j) 的最小成本
        dp = [[inf] * n for _ in range(m)]
        dp[0][0] = 0
        
        # 获取网格最大值以确定后缀数组的大小
        max_v = 0
        for r in range(m):
            for val in grid[r]:
                if val > max_v:
                    max_v = val
        
        ans = inf
        
        # 最多传送 k 次，循环 k+1 次（包含 0 次传送的情况）
        for p in range(k + 1):
            # 1. 普通移动：处理向右和向下的移动（成本为目标格子的值）
            for i in range(m):
                for j in range(n):
                    if i > 0:
                        if dp[i-1][j] + grid[i][j] < dp[i][j]:
                            dp[i][j] = dp[i-1][j] + grid[i][j]
                    if j > 0:
                        if dp[i][j-1] + grid[i][j] < dp[i][j]:
                            dp[i][j] = dp[i][j-1] + grid[i][j]
            
            # 更新到达终点的全局最小成本
            if dp[m-1][n-1] < ans:
                ans = dp[m-1][n-1]
            
            # 2. 传送准备：计算通过下一次传送到达各个格子的最小初始成本
            if p < k:
                next_dp = [[inf] * n for _ in range(m)]
                
                # min_at_val[v] 存储 grid[i][j] == v 的所有单元格中的最小成本
                min_at_val = [inf] * (max_v + 1)
                for i in range(m):
                    for j in range(n):
                        if dp[i][j] != inf:
                            v = grid[i][j]
                            if dp[i][j] < min_at_val[v]:
                                min_at_val[v] = dp[i][j]
                
                # 后缀最小值：min_at_val[v] 变为 grid[i][j] >= v 的所有单元格中的最小成本
                for v in range(max_v - 1, -1, -1):
                    if min_at_val[v+1] < min_at_val[v]:
                        min_at_val[v] = min_at_val[v+1]
                
                # 更新下一次传送后的初始成本：
                # 传送到目标格子 (i, j) 的前提是存在来源格 grid[source] >= grid[i][j]
                for i in range(m):
                    for j in range(n):
                        v_target = grid[i][j]
                        if min_at_val[v_target] < next_dp[i][j]:
                            next_dp[i][j] = min_at_val[v_target]
                
                # 进入下一轮迭代，dp 数组变为传送后的状态
                dp = next_dp
                
        return ans

复杂度分析

时间复杂度： $O (k \cdot (m \cdot n + V))$ ，其中 $m, n$ 是网格维度（最大 80）， $k$ 是最大传送次数（最大 10）， $V$ 是网格中的最大数值（最大 $10^{4}$ ）。计算量约为 $11 \times (6400 + 10000) \approx 1.8 \times 10^{5}$ ，在 Python 中运行非常快。
空间复杂度： $O (m \cdot n + V)$ 。我们只需要存储当前的 dp 数组、下一层的 next_dp 数组以及后缀最小数组。

T3651.带传送的最小路径成本 ​

T3651.带传送的最小路径成本