算法leetcode

【棋盘DP】力扣2684-矩阵中移动的最大次数

字数统计: 773字   |   阅读时长: 3分
,

摘要: 棋盘 DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来解决一个比较基础的棋盘 DP 的问题，以列号 j 为阶段，行号 i 作为附加信息。

题目

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

示例 1：
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：

  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3).
    可以证明这是能够移动的最大次数。
    示例 2：
    输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
    输出：0
    解释：从第一列的任一单元格开始都无法移动。

提示：

1
2
3
4
5
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 1e5
1 <= grid[i][j] <= 1e6

题解

算法: 棋盘DP

根据移动规则，只能从当前位置移动到右上、右、右下三个位置。也就是说，每走一步，位置一定会向右移动一格，而上下有三种可能性。

因此可以将列号 $j$ 作为动态规划的阶段，行号 $i$ 作为附加信息。因此动态规划的状态可以设计为 $dp[i][j]$ 表示从棋盘的 $(i, j)$ 位置出发，按照移动规则最多可以走的步数。

从当前阶段的状态 $(i, j)$，有可能转移到下一阶段的 $(i-1, j+1)$、$(i, j+1)$、$(i+1, j+1)$ 这三种状态。因此其状态转移方程如下：

但是要注意状态的转移是有限制的，需要 $0 \leq i+t < m$ 且 $grid[i][j] < grid[i+t][j+1]$ 时，状态才可以转移。

如果对于 $t=-1,0,1$，$(i+t, j+1)$ 全都不满足状态转移的条件，那么 $dp[i][j] = 0$，相当于动态规划的一个初始值。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import functools

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0])
        ans = 0

        for i in range(self.m):
            ans = max(ans, self.dp(i, 0))
        return ans

    @functools.lru_cache(int(1e8))
    def dp(self, i: int, j: int) -> int:
        if j == self.n - 1:
            return 0
        ans = 0
        for t in (-1, 0, 1):
            if i + t < 0 or i + t >= self.m:
                continue
            if self.grid[i][j] >= self.grid[i+t][j+1]:
                continue
            ans = max(ans, 1 + self.dp(i + t, j + 1))
        return ans
Share