##給定一個整數矩陣，找出最長遞增路徑的長度，
對于每個單元格，你可以往上，下，左，右四個方向移動， 你不能在對角線方向上移動或移動到邊界外（即不允許環繞），
示例 1:
輸入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
輸出: 4
解釋: 最長遞增路徑為 [1, 2, 6, 9]，
示例 2:
輸入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
輸出: 4
解釋: 最長遞增路徑是 [3, 4, 5, 6]，注意不允許在對角線方向上移動，
思路
記憶化搜索，
每個頂點計算一次，每條邊搜索一次，O(V)=O(mn)，O(E)=O(4V)=O(mn)，
時間復雜度O(mn)，空間復雜度O(mn)，
代碼
class Solution {
private int row;
private int col;
private int[][] dir = new int[][] {{0,1}, {1,0}, {0,-1}, {-1,0}};
private int dfs(int x, int y, int[][] mat, int[][] cache) {
if(cache[x][y] != 0) return cache[x][y];
for(int[] d : dir) {
int i = x + d[0];
int j = y + d[1];
// 每條邊搜索一次，但只遞增搜索
if(i>=0 && j>=0 && i<row && j<col && mat[x][y] < mat[i][j]) {
cache[x][y] = Math.max(cache[x][y], dfs(i, j, mat, cache));
}
}
// 作用1.初始化1
// 作用2.路徑每被成功搜索一次，新頂點長度續1
return ++cache[x][y];
}
public int longestIncreasingPath(int[][] matrix) {
row = matrix.length;
if(row < 1) return 0;
col = matrix[0].length;
int ans = 0;
int[][] cache = new int[row][col];
// 每個頂點計算一次
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
ans = Math.max(ans, dfs(i, j, matrix, cache));
}
}
return ans;
}
}
鏈接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86925.html
標籤：其他
上一篇：數值的整數次方
下一篇：調整陣列順序使奇數位于偶數前面