3651. 有传送功能的最小路径代价

Hard

题目描述

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

有两种可用的移动方式：

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

返回从 (0, 0) 到达 (m - 1, n - 1) 的最小总代价。

示例 1：

输入：grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
输出：7

示例 2：

输入：grid = [[1,2],[2,3],[3,4]], k = 1
输出：9

约束条件：

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

解题思路

这是一个典型的动态规划问题，需要考虑传送功能对路径选择的影响。

核心思想： 我们用三维DP状态 dp[t][i][j] 表示使用不超过 t 次传送到达位置 (i,j) 的最小代价。

状态转移：

普通移动：从上方或左方格子移动到当前位置，代价为当前格子的值
传送移动：从任意满足条件的位置传送到当前位置，代价为0

算法步骤：

初始化：dp[0][0][0] = 0，其他位置为无穷大
对于每个传送次数 t 从 0 到 k：
- 首先考虑普通移动：从 dp[t][i-1][j] 和 dp[t][i][j-1] 转移
- 然后考虑传送：从所有满足 grid[x][y] <= grid[i][j] 的位置 (x,y) 传送过来
最终答案为 min(dp[t][m-1][n-1]) 对所有 t

优化技巧：

传送时需要遍历所有可能的源位置，这是算法的主要时间消耗
可以通过预处理和排序来优化传送过程

这个算法的时间复杂度为 O(k × m² × n²)，空间复杂度为 O(k × m × n)。

代码实现

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        const int INF = 1e9;
        
        // dp[t][i][j] = minimum cost to reach (i,j) using at most t teleportations
        vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(m, vector<int>(n, INF)));
        
        // Initialize starting position
        dp[0][0][0] = 0;
        
        for (int t = 0; t <= k; t++) {
            // Normal moves within same teleportation count
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[t][i][j] == INF) continue;
                    
                    // Move right
                    if (j + 1 < n) {
                        dp[t][i][j + 1] = min(dp[t][i][j + 1], dp[t][i][j] + grid[i][j + 1]);
                    }
                    
                    // Move down
                    if (i + 1 < m) {
                        dp[t][i + 1][j] = min(dp[t][i + 1][j], dp[t][i][j] + grid[i + 1][j]);
                    }
                }
            }
            
            // Teleportation moves (if we have teleportations left)
            if (t < k) {
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (dp[t][i][j] == INF) continue;
                        
                        // Teleport to any valid position
                        for (int x = 0; x < m; x++) {
                            for (int y = 0; y < n; y++) {
                                if (grid[x][y] <= grid[i][j]) {
                                    dp[t + 1][x][y] = min(dp[t + 1][x][y], dp[t][i][j]);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        // Find minimum cost to reach destination
        int result = INF;
        for (int t = 0; t <= k; t++) {
            result = min(result, dp[t][m - 1][n - 1]);
        }
        
        return result;
    }
};

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        INF = float('inf')
        
        # dp[t][i][j] = minimum cost to reach (i,j) using at most t teleportations
        dp = [[[INF] * n for _ in range(m)] for _ in range(k + 1)]
        
        # Initialize starting position
        dp[0][0][0] = 0
        
        for t in range(k + 1):
            # Normal moves within same teleportation count
            for i in range(m):
                for j in range(n):
                    if dp[t][i][j] == INF:
                        continue
                    
                    # Move right
                    if j + 1 < n:
                        dp[t][i][j + 1] = min(dp[t][i][j + 1], dp[t][i][j] + grid[i][j + 1])
                    
                    # Move down
                    if i + 1 < m:
                        dp[t][i + 1][j] = min(dp[t][i + 1][j], dp[t][i][j] + grid[i + 1][j])
            
            # Teleportation moves (if we have teleportations left)
            if t < k:
                for i in range(m):
                    for j in range(n):
                        if dp[t][i][j] == INF:
                            continue
                        
                        # Teleport to any valid position
                        for x in range(m):
                            for y in range(n):
                                if grid[x][y] <= grid[i][j]:
                                    dp[t + 1][x][y] = min(dp[t + 1][x][y], dp[t][i][j])
        
        # Find minimum cost to reach destination
        result = min(dp[t][m - 1][n - 1] for t in range(k + 1))
        return result

public class Solution {
    public int MinCost(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        const int INF = int.MaxValue / 2;
        
        // dp[t][i][j] = minimum cost to reach (i,j) using at most t teleportations
        int[,,] dp = new int[k + 1, m, n];
        
        // Initialize all positions to infinity
        for (int t = 0; t <= k; t++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[t, i, j] = INF;
                }
            }
        }
        
        // Initialize starting position
        dp[0, 0, 0] = 0;
        
        for (int t = 0; t <= k; t++) {
            // Normal moves within same teleportation count
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[t, i, j] == INF) continue;
                    
                    // Move right
                    if (j + 1 < n) {
                        dp[t, i, j + 1] = Math.Min(dp[t, i, j + 1], dp[t, i, j] + grid[i][j + 1]);
                    }
                    
                    // Move down
                    if (i + 1 < m) {
                        dp[t, i + 1, j] = Math.Min(dp[t, i + 1, j], dp[t, i, j] + grid[i + 1][j]);
                    }
                }
            }
            
            // Teleportation moves (if we have teleportations left)
            if (t < k) {
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (dp[t, i, j] == INF) continue;
                        
                        // Teleport to any valid position
                        for (int x = 0; x < m; x++) {
                            for (int y = 0; y < n; y++) {
                                if (grid[x][y] <= grid[i][j]) {
                                    dp[t + 1, x, y] = Math.Min(dp[t + 1, x, y], dp[t, i, j]);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        // Find minimum cost to reach destination
        int result = INF;
        for (int t = 0; t <= k; t++) {
            result = Math.Min(result, dp[t, m - 1, n - 1]);
        }
        
        return result;
    }
}

var minCost = function(grid, k) {
    const m = grid.length;
    const n = grid[0].length;
    
    // dp[i][j][teleports] = minimum cost to reach (i,j) with teleports remaining
    const dp = Array(m).fill().map(() => 
        Array(n).fill().map(() => 
            Array(k + 1).fill(Infinity)
        )
    );
    
    dp[0][0][k] = 0;
    
    // Priority queue: [cost, row, col, teleports]
    const pq = [[0, 0, 0, k]];
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [cost, row, col, teleports] = pq.shift();
        
        if (cost > dp[row][col][teleports]) continue;
        
        if (row === m - 1 && col === n - 1) {
            return cost;
        }
        
        // Normal moves (right and down)
        const directions = [[0, 1], [1, 0]];
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow < m && newCol < n) {
                const newCost = cost + grid[newRow][newCol];
                if (newCost < dp[newRow][newCol][teleports]) {
                    dp[newRow][newCol][teleports] = newCost;
                    pq.push([newCost, newRow, newCol, teleports]);
                }
            }
        }
        
        // Teleportation moves
        if (teleports > 0) {
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    if (grid[i][j] <= grid[row][col] && (i !== row || j !== col)) {
                        if (cost < dp[i][j][teleports - 1]) {
                            dp[i][j][teleports - 1] = cost;
                            pq.push([cost, i, j, teleports - 1]);
                        }
                    }
                }
            }
        }
    }
    
    let result = Infinity;
    for (let t = 0; t <= k; t++) {
        result = Math.min(result, dp[m - 1][n - 1][t]);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(k × m² × n²)
空间复杂度	O(k × m × n)

时间复杂度说明：

外层循环遍历 k+1 种传送次数状态
对于每种状态，需要遍历所有 m×n 个格子
传送操作需要检查所有 m×n 个目标位置
总体时间复杂度为 O(k × m² × n²)

空间复杂度说明：

三维DP数组的大小为 (k+1) × m × n
空间复杂度为 O(k × m × n)

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析