LeetCode 329 - Longest Increasing Path in a Matrix

作者 QIFAN 日期 2017-01-28
LeetCode 329 - Longest Increasing Path in a Matrix

原题链接: 329. Longest Increasing Path in a Matrix


题干

给定一个矩阵,返回一个最长递增路径长度。

思路

递增是严格递增,所以不用担心成环。那样就可以使用 DFS + memo 矩阵。

(妈呀这道题一次过!)

代码:

public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int max = 1;
int M = matrix.length;
int N = matrix[0].length;
int[][] memo = new int[M][N];
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
max = Math.max(DFS(row, col, matrix, memo), max);
}
}
return max;
}
int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
private int DFS(int row, int col, int[][] matrix, int[][] memo) {
if (memo[row][col] > 0) {
return memo[row][col];
}
for (int[] d: dir) {
int x = row + d[0];
int y = col + d[1];
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[row][col] >= matrix[x][y]) {
continue;
}
memo[row][col] = Math.max(DFS(x, y, matrix, memo) + 1, memo[row][col]);
}
memo[row][col] = Math.max(memo[row][col], 1);
return memo[row][col];
}