Medium

题目描述

给定两个整数 m 和 n，分别表示网格的行数和列数。

进入单元格 (i, j) 的成本定义为 (i + 1) * (j + 1)。

还给定一个二维整数数组 waitCost，其中 waitCost[i][j] 定义在该单元格等待的成本。

路径总是从第 1 秒进入单元格 (0, 0) 开始，并支付进入成本。

每一步，你需要遵循交替模式：

  • 在奇数秒，你必须向右或向下移动到相邻单元格，支付其进入成本。
  • 在偶数秒，你必须在原地等待一秒，并在该秒期间支付 waitCost[i][j]。

返回到达 (m - 1, n - 1) 所需的最小总成本。

示例 1：

输入：m = 1, n = 2, waitCost = [[1,2]]
输出：3

示例 2：

输入：m = 2, n = 2, waitCost = [[3,5],[2,4]]
输出：9

示例 3：

输入：m = 2, n = 3, waitCost = [[6,1,4],[3,2,5]]
输出：16

约束条件：

  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • waitCost.length == m
  • waitCost[0].length == n
  • 0 <= waitCost[i][j] <= 10^5

解题思路

这是一道动态规划题目，关键在于理解移动规律和成本计算。

核心思路分析：

  1. 移动模式是固定的：奇数秒移动，偶数秒等待
  2. 从 (0,0) 到达任何位置 (i,j) 需要的移动次数是 i + j 步
  3. 如果移动次数为奇数，最后一步是移动（奇数秒），不需要等待
  4. 如果移动次数为偶数，最后一步是等待（偶数秒），需要支付等待成本

状态转移： 设 dp[i][j] 表示到达位置 (i,j) 的最小成本。状态转移方程为：

  • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + entryCost + waitCost
  • 其中 entryCost = (i+1) * (j+1)
  • waitCost 根据移动步数的奇偶性决定是否需要

边界条件：

  • dp[0][0] = 1（进入起点的成本）
  • 第一行和第一列需要特殊处理

优化细节：

  • 由于只需要前一行和前一列的信息，可以使用滚动数组优化空间复杂度
  • 最终答案需要根据到达终点的步数奇偶性决定是否减去最后的等待成本

代码实现

class Solution {
public:
    long long minCost(int m, int n, vector<vector<int>>& waitCost) {
        vector<vector<long long>> dp(m, vector<long long>(n, LLONG_MAX));
        
        // 初始化起点
        dp[0][0] = 1;
        
        // 填充第一行
        for (int j = 1; j < n; j++) {
            int steps = j;
            long long entryCost = 1LL * (0 + 1) * (j + 1);
            long long waitCostVal = (steps % 2 == 0) ? waitCost[0][j] : 0;
            dp[0][j] = dp[0][j-1] + entryCost + waitCostVal;
        }
        
        // 填充第一列
        for (int i = 1; i < m; i++) {
            int steps = i;
            long long entryCost = 1LL * (i + 1) * (0 + 1);
            long long waitCostVal = (steps % 2 == 0) ? waitCost[i][0] : 0;
            dp[i][0] = dp[i-1][0] + entryCost + waitCostVal;
        }
        
        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int steps = i + j;
                long long entryCost = 1LL * (i + 1) * (j + 1);
                long long waitCostVal = (steps % 2 == 0) ? waitCost[i][j] : 0;
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + entryCost + waitCostVal;
            }
        }
        
        return dp[m-1][n-1];
    }
};

class Solution:
    def minCost(self, m: int, n: int, waitCost: List[List[int]]) -> int:
        dp = [[float('inf')] * n for _ in range(m)]
        
        # 初始化起点
        dp[0][0] = 1
        
        # 填充第一行
        for j in range(1, n):
            steps = j
            entry_cost = (0 + 1) * (j + 1)
            wait_cost_val = waitCost[0][j] if steps % 2 == 0 else 0
            dp[0][j] = dp[0][j-1] + entry_cost + wait_cost_val
        
        # 填充第一列
        for i in range(1, m):
            steps = i
            entry_cost = (i + 1) * (0 + 1)
            wait_cost_val = waitCost[i][0] if steps % 2 == 0 else 0
            dp[i][0] = dp[i-1][0] + entry_cost + wait_cost_val
        
        # 填充其余位置
        for i in range(1, m):
            for j in range(1, n):
                steps = i + j
                entry_cost = (i + 1) * (j + 1)
                wait_cost_val = waitCost[i][j] if steps % 2 == 0 else 0
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + entry_cost + wait_cost_val
        
        return dp[m-1][n-1]

public class Solution {
    public long MinCost(int m, int n, int[][] waitCost) {
        long[,] dp = new long[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = long.MaxValue;
            }
        }
        
        // 初始化起点
        dp[0, 0] = 1;
        
        // 填充第一行
        for (int j = 1; j < n; j++) {
            int steps = j;
            long entryCost = (0 + 1) * (j + 1);
            long waitCostVal = (steps % 2 == 0) ? waitCost[0][j] : 0;
            dp[0, j] = dp[0, j-1] + entryCost + waitCostVal;
        }
        
        // 填充第一列
        for (int i = 1; i < m; i++) {
            int steps = i;
            long entryCost = (i + 1) * (0 + 1);
            long waitCostVal = (steps % 2 == 0) ? waitCost[i][0] : 0;
            dp[i, 0] = dp[i-1, 0] + entryCost + waitCostVal;
        }
        
        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int steps = i + j;
                long entryCost = (i + 1) * (j + 1);
                long waitCostVal = (steps % 2 == 0) ? waitCost[i][j] : 0;
                dp[i, j] = Math.Min(dp[i-1, j], dp[i, j-1]) + entryCost + waitCostVal;
            }
        }
        
        return dp[m-1, n-1];
    }
}

var minCost = function(m, n, waitCost) {
    const dp = Array(m).fill().map(() => Array(n).fill(Infinity));
    
    dp[0][0] = 1;
    
    const queue = [[0, 0, 1, 1]];
    
    while (queue.length > 0) {
        const [row, col, cost, time] = queue.shift();
        
        if (cost > dp[row][col]) continue;
        
        if (time % 2 === 0) {
            const waitTotal = cost + waitCost[row][col];
            if (waitTotal < dp[row][col]) {
                dp[row][col] = waitTotal;
                queue.push([row, col, waitTotal, time + 1]);
            }
        } else {
            if (row + 1 < m) {
                const newCost = cost + (row + 2) * (col + 1);
                if (newCost < dp[row + 1][col]) {
                    dp[row + 1][col] = newCost;
                    queue.push([row + 1, col, newCost, time + 1]);
                }
            }
            
            if (col + 1 < n) {
                const newCost = cost + (row + 1) * (col + 2);
                if (newCost < dp[row][col + 1]) {
                    dp[row][col + 1] = newCost;
                    queue.push([row, col + 1, newCost, time + 1]);
                }
            }
        }
    }
    
    return dp[m - 1][n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n) - 需要遍历每个网格单元格一次
空间复杂度O(m × n) - 使用二维dp数组存储中间结果