3148.矩阵中的最大得分

链接：3148.矩阵中的最大得分
难度：Medium
标签：数组、动态规划、矩阵
简介：给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。你可以从 任一 单元格开始，并且必须至少移动一次。返回你能得到的 最大 总得分。

题解 1 - python

• 编辑时间：2024-08-15
• 执行用时：399ms
• 内存消耗：28.66MB
• 编程语言：python
• 解法介绍：dp[i][j]表示以grid[i-1][j-1]为右下角顶点时，区间内的最小值

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