What is the state transition dynamic programming approach for this problem?

State transition dynamic programming involves calculating the score of each move based on previously computed results, updating the table to reflect the maximum score achievable from each cell.

Can I move in directions other than right or down in the grid?

No, you are only allowed to move to the bottom or right cells in the grid.

How does the maximum score calculation depend on previous moves?

The score of each move is calculated based on the difference between the current and destination cell values, with previous moves impacting the score accumulation.

What’s the best strategy to maximize the score in the grid?

The best strategy involves selecting moves that give the highest possible score difference while ensuring that moves are restricted to the allowed directions (right or down).

What are common mistakes people make in this problem?

A common mistake is not properly updating the dynamic programming table to track the optimal path, or misinterpreting the allowed directions for movement.

#3148

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

矩阵中的最大得分

给你一个由正整数组成、大小为 m x n 的矩阵 grid 。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。你可以从任一单元格开始，并且必须至少移动一次。返回你能得到的最大 …

数组动态规划矩阵

题目描述

给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。

你可以从任一单元格开始，并且必须至少移动一次。

返回你能得到的最大总得分。

示例 1：

输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]

输出：9

解释：从单元格 (0, 1) 开始，并执行以下移动：
- 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
- 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。
总得分为 2 + 7 = 9 。

示例 2：

输入：grid = [[4,3,2],[3,2,1]]

输出：-1

解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

lightbulb

解题思路

方法一：动态规划

根据题目描述，如果我们经过的单元格的值依次是 $c_1, c_2, \cdots, c_k$ ，那么我们的得分就是 $c_2 - c_1 + c_3 - c_2 + \cdots + c_k - c_{k-1} = c_k - c_1$ 。因此，问题转化为：对于矩阵的每个单元格 $(i, j)$ ，如果我们将其作为终点，那么起点的最小值是多少。

我们可以使用动态规划来解决这个问题。我们定义 $f[i][j]$ 表示以 $(i, j)$ 为终点的路径的最小值。那么我们可以得到状态转移方程：

f[i][j] = \min(f[i-1][j], f[i][j-1], grid[i][j])

那么答案为 $\textit{grid}[i][j] - \min(f[i-1][j], f[i][j-1])$ 的最大值。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        f = [[0] * len(grid[0]) for _ in range(len(grid))]
        ans = -inf
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                mi = inf
                if i:
                    mi = min(mi, f[i - 1][j])
                if j:
                    mi = min(mi, f[i][j - 1])
                ans = max(ans, x - mi)
                f[i][j] = min(x, mi)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests ability to apply dynamic programming to state transition problems.
question_mark
Looks for optimization techniques, especially in terms of grid traversal.
question_mark
Assesses understanding of path selection and maximizing score.

warning

常见陷阱

外企场景

error
Forgetting to update the DP table in a way that accounts for previously computed optimal scores.
error
Incorrectly assuming that you can move in any direction, when only bottom or right are allowed.
error
Not accounting for the minimum move requirement or making unnecessary moves.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different grid sizes or constraints on cell values may require more efficient algorithms.
arrow_right_alt
Variation in starting point could lead to different optimal paths.
arrow_right_alt
Incorporating additional constraints like a limited number of moves could add complexity.

help

常见问题

外企场景

继续练习

#3122 使矩阵满足条件的最少操作次数 #3225 网格图操作后的最大分数 #3256 放三个车的价值之和最大 I