Medium

题目描述

给你一个 m x n 的网格，每个单元格包含值 0、1 或 2 中的一个。同时给你一个整数 k。

你从左上角 (0, 0) 开始，想要到达右下角 (m - 1, n - 1)，只能向右或向下移动。

每个单元格根据其值贡献特定的分数并产生相关的代价：

  • 0：为你的分数增加 0，代价为 0。
  • 1：为你的分数增加 1，代价为 1。
  • 2：为你的分数增加 2，代价为 1。

返回在不超过总代价 k 的情况下可以达到的最大分数，如果不存在有效路径则返回 -1。

注意：如果你到达最后一个单元格但总代价超过 k，则路径无效。

示例 1：

输入：grid = [[0, 1],[2, 0]], k = 1
输出：2

示例 2：

输入：grid = [[0, 1],[1, 2]], k = 1
输出：-1

约束条件：

  • 1 <= m, n <= 200
  • 0 <= k <= 10^3
  • grid[0][0] == 0
  • 0 <= grid[i][j] <= 2

解题思路

这是一个典型的动态规划问题，需要在满足代价约束的前提下求最大分数。

核心思路：

我们定义三维动态规划状态：dp[i][j][c] 表示到达位置 (i,j) 且总代价恰好为 c 时能获得的最大分数。

状态转移：

对于每个位置 (i,j)，我们可以从上方 (i-1,j) 或左方 (i,j-1) 到达。根据当前格子的值计算代价和分数：

  • 代价 = grid[i][j] == 0 ? 0 : 1
  • 分数 = grid[i][j]

状态转移方程为：

dp[i][j][c] = max(dp[i-1][j][c-cost] + score, dp[i][j-1][c-cost] + score)

边界条件：

  • dp[0][0][0] = 0（起点代价为0，分数为0）

优化策略：

由于我们只关心是否能到达终点以及最大分数，可以使用 -1 表示无法到达的状态，用有效值表示能到达时的最大分数。

最终答案： 遍历 dp[m-1][n-1][0] 到 dp[m-1][n-1][k] 中的最大值，如果都是 -1 则返回 -1。

时间复杂度为 O(m×n×k)，空间复杂度为 O(m×n×k)。由于约束条件较小，这个复杂度是可以接受的。

代码实现

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k + 1, -1)));
        
        dp[0][0][0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cost = (grid[i][j] == 0) ? 0 : 1;
                int score = grid[i][j];
                
                for (int c = cost; c <= k; c++) {
                    if (i > 0 && dp[i-1][j][c-cost] != -1) {
                        dp[i][j][c] = max(dp[i][j][c], dp[i-1][j][c-cost] + score);
                    }
                    if (j > 0 && dp[i][j-1][c-cost] != -1) {
                        dp[i][j][c] = max(dp[i][j][c], dp[i][j-1][c-cost] + score);
                    }
                }
            }
        }
        
        int result = -1;
        for (int c = 0; c <= k; c++) {
            if (dp[m-1][n-1][c] != -1) {
                result = max(result, dp[m-1][n-1][c]);
            }
        }
        
        return result;
    }
};

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[-1] * (k + 1) for _ in range(n)] for _ in range(m)]
        
        dp[0][0][0] = 0
        
        for i in range(m):
            for j in range(n):
                cost = 0 if grid[i][j] == 0 else 1
                score = grid[i][j]
                
                for c in range(cost, k + 1):
                    if i > 0 and dp[i-1][j][c-cost] != -1:
                        dp[i][j][c] = max(dp[i][j][c], dp[i-1][j][c-cost] + score)
                    if j > 0 and dp[i][j-1][c-cost] != -1:
                        dp[i][j][c] = max(dp[i][j][c], dp[i][j-1][c-cost] + score)
        
        result = -1
        for c in range(k + 1):
            if dp[m-1][n-1][c] != -1:
                result = max(result, dp[m-1][n-1][c])
        
        return result

public class Solution {
    public int MaxPathScore(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int[,,] dp = new int[m, n, k + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int c = 0; c <= k; c++) {
                    dp[i, j, c] = -1;
                }
            }
        }
        
        dp[0, 0, 0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cost = grid[i][j] == 0 ? 0 : 1;
                int score = grid[i][j];
                
                for (int c = cost; c <= k; c++) {
                    if (i > 0 && dp[i-1, j, c-cost] != -1) {
                        dp[i, j, c] = Math.Max(dp[i, j, c], dp[i-1, j, c-cost] + score);
                    }
                    if (j > 0 && dp[i, j-1, c-cost] != -1) {
                        dp[i, j, c] = Math.Max(dp[i, j, c], dp[i, j-1, c-cost] + score);
                    }
                }
            }
        }
        
        int result = -1;
        for (int c = 0; c <= k; c++) {
            if (dp[m-1, n-1, c] != -1) {
                result = Math.Max(result, dp[m-1, n-1, c]);
            }
        }
        
        return result;
    }
}

var maxPathScore = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const dp = Array(m).fill().map(() => 
        Array(n).fill().map(() => Array(k + 1).fill(-1))
    );
    
    dp[0][0][0] = 0;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const cost = grid[i][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 m 和 n 分别是网格的行数和列数，k 是代价限制。我们需要遍历每个位置的每个可能代价值，因此时间复杂度为 O(m × n × k)。空间复杂度同样为 O(m × n × k)，用于存储三维动态规划数组。