2684-矩阵中移动的最大次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个下标从 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：

![](https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png)
**输入：** grid = [[3,2,4],[2,1,9],[1,1,7]]
**输出：** 0
**解释：** 从第一列的任一单元格开始都无法移动。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 105
  • 1 <= grid[i][j] <= 106

视频讲解 （周赛 345 第三题）

方法一：动态规划

前置知识：动态规划、记忆化搜索

见 动态规划入门：从记忆化搜索到递推 。

记忆化搜索

写一个递归函数 dfs}(i,j)，返回并记录从 (i,j) 出发时的答案。

枚举向右边的三个方向走，如果对应的格子没有出界，且格子值大于 grid}[i][j]，则有

\textit{dfs}(i,j) = \max(\textit{dfs}(i-1,j+1)+1,\textit{dfs}(i,j+1)+1,\textit{dfs}(i+1,j+1)+1)

递归边界：dfs}(i,n-1)=0。

递归入口：dfs}(i,0)。取最大值即为答案。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i: int, j: int) -> int:
            if j == n - 1:
                return 0
            res = 0
            for k in i - 1, i, i + 1:
                if 0 <= k < m and grid[k][j + 1] > grid[i][j]:
                    res = max(res, dfs(k, j + 1) + 1)
            return res
        return max(dfs(i, 0) for i in range(m))
[sol1-Go]
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
26
27
28
29
30
31
32
33
34
func maxMoves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1 // -1 表示没被计算过
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) (res int) {
		if j == n-1 {
			return
		}
		p := &memo[i][j]
		if *p != -1 {
			return *p
		}
		for k := max(i-1, 0); k < min(i+2, m); k++ {
			if grid[k][j+1] > grid[i][j] {
				res = max(res, dfs(k, j+1)+1)
			}
		}
		*p = res // 记忆化
		return
	}
	for i := 0; i < m; i++ {
		ans = max(ans, dfs(i, 0))
	}
	return
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn)，其中 m 和 n 分别为 grid 的行数和列数。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(mn)，单个状态的计算时间为 \mathcal{O}(1)，因此时间复杂度为 \mathcal{O}(mn)。
  • 空间复杂度：\mathcal{O}(mn)。

1:1 翻译成递推

根据视频中讲的，我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

做法：

  • dfs 改成 f 数组。
  • 递归改成循环（每个参数都对应一层循环）。由于递归是从左向右移动，所以递推是从右到左移动。
  • 递归边界改成 f 数组的初始值。本题可以直接把 f[i][j] 初始化为 0。
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]
        for j in range(n - 2, -1, -1):
            for i, row in enumerate(grid):
                for k in i - 1, i, i + 1:
                    if 0 <= k < m and grid[k][j + 1] > row[j]:
                        f[i][j] = max(f[i][j], f[k][j + 1] + 1)
        return max(row[0] for row in f)
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        var f = new int[m][n];
        for (int j = n - 2; j >= 0; j--)
            for (int i = 0; i < m; i++)
                for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, m); k++)
                    if (grid[k][j + 1] > grid[i][j])
                        f[i][j] = Math.max(f[i][j], f[k][j + 1] + 1);
        int ans = 0;
        for (int i = 0; i < m; i++)
            ans = Math.max(ans, f[i][0]);
        return ans;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxMoves(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), f[m][n];
        memset(f, 0, sizeof(f));
        for (int j = n - 2; j >= 0; j--)
            for (int i = 0; i < m; i++)
                for (int k = max(i - 1, 0); k < min(i + 2, m); k++)
                    if (grid[k][j + 1] > grid[i][j])
                        f[i][j] = max(f[i][j], f[k][j + 1] + 1);
        int ans = 0;
        for (int i = 0; i < m; i++)
            ans = max(ans, f[i][0]);
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxMoves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	for j := n - 2; j >= 0; j-- {
		for i, row := range grid {
			for k := max(i-1, 0); k < min(i+2, m); k++ {
				if grid[k][j+1] > row[j] {
					f[i][j] = max(f[i][j], f[k][j+1]+1)
				}
			}
		}
	}
	for _, r := range f {
		ans = max(ans, r[0])
	}
	return
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn)，其中 m 和 n 分别为 grid 的行数和列数。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(mn)，单个状态的计算时间为 \mathcal{O}(1)，因此时间复杂度为 \mathcal{O}(mn)。
  • 空间复杂度：\mathcal{O}(mn)。

注：利用滚动数组，空间可以进一步优化至 O(m)。

相似题目：网格图 DP

方法二：BFS

也可以用 BFS 做，每一轮向右搜索一列。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = range(m)
        vis = [-1] * m
        for j in range(n - 1):
            tmp = q
            q = []
            for i in tmp:
                for k in i - 1, i, i + 1:
                    if 0 <= k < m and vis[k] != j and grid[k][j + 1] > grid[i][j]:
                        vis[k] = j  # 时间戳标记，避免重复创建 vis 数组
                        q.append(k)
            if len(q) == 0:
                return j
        return n - 1
[sol3-Go]
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
26
27
func maxMoves(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	vis := make([]int, m)
	q := make([]int, m)
	for i := range q {
		q[i] = i
	}
	for j := 0; j < n-1; j++ {
		tmp := q
		q = nil
		for _, i := range tmp {
			for k := max(i-1, 0); k < min(i+2, m); k++ {
				if vis[k] != j+1 && grid[k][j+1] > grid[i][j] {
					vis[k] = j + 1 // 时间戳标记，避免重复创建 vis 数组
					q = append(q, k)
				}
			}
		}
		if q == nil {
			return j
		}
	}
	return n - 1
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn)，其中 m 和 n 分别为 grid 的行数和列数。
  • 空间复杂度：\mathcal{O}(m)。
 Comments
On this page
2684-矩阵中移动的最大次数
  1. 方法一：动态规划
    1. 前置知识：动态规划、记忆化搜索
    2. 记忆化搜索
    3. 1:1 翻译成递推
    4. 相似题目：网格图 DP
  • 方法二：BFS