Medium

题目描述

给你一个 m x n 的整数矩阵 grid ，矩阵中的值为 0 到 m * n - 1 内的不同整数。你可以在这个矩阵中，从一个单元格移动到 下一行 任意一个单元格。也就是说，如果你在 (x, y) 且 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1) 中任何一个单元格。注意： 在最后一行中的单元格不能触发移动。

每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。

grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。

示例 1：

输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出：17
解释：最小代价的路径是 5 -> 0 -> 1 。
- 路径经过单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。

示例 2：

输入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
输出：6
解释：最小代价的路径是 2 -> 3 。
- 路径经过单元格值之和 2 + 3 = 5 。
- 从 2 移动到 3 的代价为 1 。
路径总代价为 5 + 1 = 6 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • grid 由从 0 到 m * n - 1 的不同整数组成
  • moveCost.length == m * n
  • moveCost[i].length == n
  • 1 <= moveCost[i][j] <= 100

解题思路

解题思路

这是一道典型的动态规划问题。我们需要找到从第一行任意位置到最后一行任意位置的最小路径代价。

核心思想：

  1. 定义状态：dp[i][j] 表示到达第 i 行第 j 列位置的最小代价
  2. 状态转移：对于位置 (i,j)，它可以从上一行的任意位置 (i-1,k) 转移而来
  3. 转移方程：dp[i][j] = min(dp[i-1][k] + moveCost[grid[i-1][k]][j]) + grid[i][j]

算法步骤：

  1. 初始化第一行：dp[0][j] = grid[0][j]
  2. 逐行计算：对于每一行的每个位置，考虑从上一行所有位置转移过来的最小代价
  3. 最终答案：最后一行中的最小值

优化思路：

  • 可以使用滚动数组优化空间复杂度，只保存当前行和上一行的状态
  • 由于每行都要遍历上一行所有位置，时间复杂度为 O(m*n²)

这种方法保证了我们能找到全局最优解，因为每个状态都是基于之前的最优状态计算得出的。

代码实现

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[0][j] = grid[0][j];
        }
        
        // 逐行计算最小代价
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    int cost = dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j];
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        
        // 返回最后一行的最小值
        return *min_element(dp[m-1].begin(), dp[m-1].end());
    }
};

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        
        # 初始化第一行
        for j in range(n):
            dp[0][j] = grid[0][j]
        
        # 逐行计算最小代价
        for i in range(1, m):
            for j in range(n):
                for k in range(n):
                    cost = dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j]
                    dp[i][j] = min(dp[i][j], cost)
        
        # 返回最后一行的最小值
        return min(dp[m-1])

public class Solution {
    public int MinPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.Length, n = grid[0].Length;
        int[,] dp = new int[m, n];
        
        // 初始化所有位置为最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[0, j] = grid[0][j];
        }
        
        // 逐行计算最小代价
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    int cost = dp[i-1, k] + moveCost[grid[i-1][k]][j] + grid[i][j];
                    dp[i, j] = Math.Min(dp[i, j], cost);
                }
            }
        }
        
        // 返回最后一行的最小值
        int result = int.MaxValue;
        for (int j = 0; j < n; j++) {
            result = Math.Min(result, dp[m-1, j]);
        }
        return result;
    }
}

var minPathCost = function(grid, moveCost) {
    const m = grid.length, n = grid[0].length;
    const dp = Array(m).fill().map(() => Array(n).fill(Infinity));
    
    // 初始化第一行
    for (let j = 0; j < n; j++) {
        dp[0][j] = grid[0][j];
    }
    
    // 逐行计算最小代价
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                const cost = dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    
    // 返回最后一行的最小值
    return Math.min(...dp[m-1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n²)m行n列，每个位置需要考虑上一行的n个位置
空间复杂度O(m × n)需要m×n的二维数组存储状态

优化空间复杂度： 可以使用滚动数组将空间复杂度优化到 O(n)，只保存当前行和上一行的状态。

相关题目