java某个起点出发的最长路径_【leetcode-动态规划】矩阵中的最长递增路径
【leetcode-動(dòng)態(tài)規(guī)劃】矩陣中的最長遞增路徑
題目：
給定一個(gè)整數(shù)矩陣，找出最長遞增路徑的長度。
對于每個(gè)單元格，你可以往上，下，左，右四個(gè)方向移動(dòng)。 你不能在對角線方向上移動(dòng)或移動(dòng)到邊界外(即不允許環(huán)繞)。
示例 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]
。注意不允許在對角線方向上移動(dòng)。
思路：
DFS+dp
1、dp[i][j]表示數(shù)組中以(i,j)為起點(diǎn)的最長遞增路徑的長度，初始將dp數(shù)組都賦為0，
2、遞歸調(diào)用時(shí)，遇到某個(gè)位置(x, y), 如果dp[x][y]不為0的話，我們直接返回dp[x][y]即可，不需要重復(fù)計(jì)算。
3、以數(shù)組中每個(gè)位置都為起點(diǎn)調(diào)用遞歸來做，比較找出最大值。在以一個(gè)位置為起點(diǎn)用DFS搜索時(shí)，對其四個(gè)相鄰位置進(jìn)行判斷，
如果相鄰位置的值大于上一個(gè)位置，則對相鄰位置繼續(xù)調(diào)用遞歸，并更新一個(gè)最大值，搜素完成后返回即可。
java代碼：
class Solution {
private int[][] paths = {{0,1},{0,-1},{1,0},{-1,0}};
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
return 0;
}
int max = 0;
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
for (int i=0; i
for (int j=0; j
max = Math.max(max, dfs(matrix, dp, row, col, i, j));
}
}
return max;
}
private int dfs(int[][] matrix, int[][] dp, int row, int col, int i, int j) {
if (dp[i][j] > 0) {
return dp[i][j];
}
int max = 1;
for (int[] path : paths) {
int x = i + path[0];
int y = j + path[1];
// 可以繼續(xù)搜索
if (x >= 0 && x = 0 && y < col && matrix[x][y] > matrix[i][j]) {
int len = 1 + dfs(matrix, dp, row, col, x, y);
max = Math.max(max, len);
}
}
dp[i][j] = max;
return max;
}
}
總結(jié)
以上是生活随笔為你收集整理的java某个起点出发的最长路径_【leetcode-动态规划】矩阵中的最长递增路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
