329. Longest Increasing Path in a Matrix

Question

Given an m x n integers matrix, return *the length of the longest increasing path in *matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Solution

第一次就通过DFS和DP的知识自己摸索出了记忆化搜索,非常开心!: )

记忆化搜索,采用DFS搜索,并动态规划的思想保存搜索结果。

递归计算从x, y点出发的最大长度,并在递归中记录子位置的最大长度。
通过子位置的最大长度对递归树进行剪枝。

记忆化搜索

初始化一个memo[][]数组,记录已经搜索过的x, y位置的最大长度。
对所有下一个位置进行DFS搜索,如果越界或不满足递增规律,则返回最大长度1。
(这里应该返回0,但是为了下一步的记忆化搜索判断的遍历因此返回1。如果返回0的话则后面返回最大值不需要-1,但此时由于会重复搜索因此速度会降低。)

如果x, y的位置已经搜索过了(即memo[x][y] != 0),则直接返回memo[x][y]的值+1。

搜索完所有位置的最大长度,将其中的最大值保存在memo[][]中。
最后返回最大值+1。

将每个位置遍历,返回memo[][]中的最大值。

Code

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
class Solution {
int[][] mat, memo, moves = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int m, n, max;

public int longestIncreasingPath(int[][] matrix) {
mat = matrix;
m = matrix.length;
n = matrix[0].length;
memo = new int[m][n];

max = 0;
for(int x = 0; x < m; x++){
for(int y = 0; y < n; y++){
dfs(x, y, -1);
max = Math.max(max, memo[x][y]);
}
}
return max;
}

private int dfs(int x, int y, int parent){
if(x < 0 || y < 0 || x >= m || y >= n || parent >= mat[x][y]) return 1;
if(memo[x][y] != 0) return memo[x][y] + 1;
int best = 0;
for(int[] move : moves){
int count = dfs(x + move[0], y + move[1], mat[x][y]);
best = Math.max(best, count);
}
memo[x][y] = best;
return best + 1;
}
}
Author

Xander

Posted on

2022-05-19

Updated on

2022-05-19

Licensed under

Comments