↓Skip to main content
  1. Posts/

LeetCode-3148 矩阵中的最大得分

·1 min·
Table of Contents

LeetCode-3148 矩阵中的最大得分 #

Solution 1 #

在一条路径中, 涉及中间节点的值的计算会被抵消掉, 所以考虑起点和终点的差值即可. 维护 $dp[i][j]= \min({grid[x][y], 0\leq x\leq i, 0\leq y\leq j})$ , 那么以 $grid[i][j]$ 为终点的路径最大得分就是 $grid[i][j] - \min(dp[i - 1][j], dp[i][j - 1])$ . 遍历并维护答案.

代码如下:

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = -inf
        for i in range(m):
            for j in range(n):
                res = grid[i][j]
                if i > 0:
                    ans = max(ans, grid[i][j] - grid[i - 1][j])
                    res = min(res, grid[i - 1][j])
                if j > 0:
                    ans = max(ans, grid[i][j] - grid[i][j - 1])
                    res = min(res, grid[i][j - 1])
                grid[i][j] = res
        return ans