🌀 初学者友好指南 “Minimum Cost Path with Teleportations” - LeetCode 3651 (C++, Python, JavaScript)

Source: Dev.to

问题概述

在网格中导航是经典的编码挑战，但加入传送后游戏规则会完全改变。
给定：

• 一个大小为 m x n 的二维网格，每个单元格包含一个费用值。
• 一个整数 k，表示最多可以使用传送的次数。
• 两种移动规则：
  1. 普通移动 – 向右或向下移动，费用为目标单元格的值。
  2. 传送 – 跳到任意 ≤ 当前单元格值的单元格，费用为 0。

目标： 计算从左上角单元格 (0,0) 到右下角单元格 (m‑1,n‑1) 的最小总费用。

方法

标准动态规划（无传送）

在没有传送的情况下，问题简化为一个简单的 DP：

dp[i][j] = grid[i][j] + min(dp[i‑1][j], dp[i][j‑1])

引入传送

传送非常强大，因为它不消耗代价，但只能目标值不大于当前单元格值的格子，并且最多只能使用 k 次此类跳跃。

我们基于使用的传送次数，以层（或“轮次”）的方式求解问题：

1. 对于每个传送计数 t = 0 … k，我们维护到达每个可能单元格值的最小费用。
2. 一个后缀最小数组 suf_min_f[value] 保存到达值 ≥ value 的任意单元格的最小费用。这使我们能够在 O(1) 时间内回答“传送到值为 x 的单元格是否更便宜？”
3. 在逐行扫描网格时，我们更新：
   • standard_move – 来自左侧或上方的费用加上当前单元格的值。
   • teleport_move – suf_min_f[x]（值 ≥ x 的最佳可达单元格的费用）。
   • 这两者的最小值即为当前单元格的新费用。
4. 对给定 t 完成整个网格的处理后，我们为下一次迭代重新构建 suf_min_f。

如果在迭代之间 suf_min_f 没有变化，算法会提前停止。

复杂度

• 时间复杂度： O(k * m * n) – 每层扫描整个网格一次。
• 空间复杂度： O(mx + n)，其中 mx 为单元格的最大值（用于后缀数组），加上一行线性 DP。

示例

grid = [[1,3,3],
        [2,5,4],
        [4,3,5]]
k = 2

1. 从 (0,0) 开始，费用为 0。
2. 向下移动到 (1,0) → 费用 2。
3. 向右移动到 (1,1) → 费用 7。
4. 从 (1,1)（值为 5）传送到 (2,2)（值为 5），免费。
5. 到达终点，总费用 7。

答案是 7。

解决方案实现

C++ (GNU‑C++17)

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();

        // Edge case: free teleport possible
        if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

        int mx = 0;
        for (auto& row : grid)
            for (int v : row) mx = max(mx, v);

        const int INF = 2e9;
        vector<int> suf_min_f(mx + 2, INF);
        vector<int> f(n + 1, INF);

        for (int t = 0; t <= k; ++t) {
            vector<int> min_f(mx + 1, INF);
            vector<int> new_f(n + 1, INF);
            if (t == 0) new_f[1] = 0;   // start cost

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int x = grid[i][j];
                    int standard = min(new_f[j], new_f[j + 1]) + x;
                    if (i == 0 && j == 0 && t == 0) standard = 0;
                    new_f[j + 1] = min(standard, suf_min_f[x]);
                    min_f[x] = min(min_f[x], new_f[j + 1]);
                }
            }
            f = new_f;

            // rebuild suffix minima
            vector<int> new_suf(mx + 2, INF);
            for (int v = mx; v >= 0; --v)
                new_suf[v] = min(new_suf[v + 1], min_f[v]);

            if (suf_min_f == new_suf) break;
            suf_min_f.swap(new_suf);
        }
        return f[n];
    }
};

Python 3

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 = max(max(row) for row in grid)
        INF = float('inf')
        suf_min_f = [INF] * (mx + 2)
        f = [INF] * (n + 1)

        for t in range(k + 1):
            min_f = [INF] * (mx + 1)
            new_f = [INF] * (n + 1)
            if t == 0:
                new_f[1] = 0   # start cost

            for i in range(m):
                for j in range(n):
                    x = grid[i][j]
                    standard = min(new_f[j], new_f[j + 1]) + x
                    if i == 0 and j == 0 and t == 0:
                        standard = 0
                    new_f[j + 1] = min(standard, suf_min_f[x])
                    min_f[x] = min(min_f[x], new_f[j + 1])

            f = new_f

            # rebuild suffix minima
            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]

JavaScript (Node.js)

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var minCost = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

    let mx = 0;
    for (let row of grid)
        for (let v of row) mx = Math.max(mx, v);

    const INF = Number.MAX_SAFE_INTEGER;
    let sufMinF = new Array(mx + 2).fill(INF);
    let f = new Array(n + 1).fill(INF);

    for (let t = 0; t <= k; ++t) {
        const minF = new Array(mx + 1).fill(INF);
        const newF = new Array(n + 1).fill(INF);
        if (t === 0) newF[1] = 0;   // start cost

        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                const x = grid[i][j];
                const standard = Math.min(newF[j], newF[j + 1]) + x;
                const best = Math.min(standard, sufMinF[x]);
                newF[j + 1] = best;
                minF[x] = Math.min(minF[x], best);
            }
        }
        f = newF;

        // rebuild suffix minima
        const nextSuf = new Array(mx + 2).fill(INF);
        for (let v = mx; v >= 0; --v)
            nextSuf[v] = Math.min(nextSuf[v + 1], minF[v]);

        if (JSON.stringify(sufMinF) === JSON.stringify(nextSuf)) break;
        sufMinF = nextSuf;
    }
    return

f[n];
};

关键要点

• 状态扩展（添加传送计数维度）使我们能够对每一次允许的传送复用相同的动态规划逻辑。
• 后缀最小值提供 O(1) 查询，用于获取“所有值 ≥ x 的单元格中最便宜的成本”。
• 空间优化：只需要前一次传送计数的结果，从而保持线性内存使用。

这种模式出现在许多实际的路由问题中，例如送货无人机可以驾驶（成本高）或在高空平台之间飞行（免费但受限）。