文章目錄：
- 題目要求
- 解題思路
- 具體實(shí)現(xiàn)
- 改進(jìn)之路
- 總結(jié)
1. 題目要求
給定一個(gè)整數(shù)矩陣，找出最長遞增路徑的長度。
對(duì)于每個(gè)單元格，你可以往上，下，左，右四個(gè)方向移動(dòng)。 你不能在對(duì)角線方向上移動(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]。注意不允許在對(duì)角線方向上移動(dòng)。
--題目來源于 leetcode
2. 解題思路
2.1 二維數(shù)組存儲(chǔ)數(shù)據(jù) int[][] matrix，int[][] dpn 記錄路徑.
2.2 參考動(dòng)態(tài)規(guī)劃之記憶化搜索 滑雪問題:
上圖顯示為R*C的雪場，R是行數(shù)，C是列數(shù)。圓圈內(nèi)的數(shù)字表示的是雪場的海拔高度h，根據(jù)常識(shí)我們知道，滑雪只有從上往下滑行才可能滑的動(dòng)，現(xiàn)在我們想要求出能夠滑行的最長距離，上面的例子我們可以很直接判斷出25-24-......-1這個(gè)順時(shí)針方向螺旋的滑雪方式可以滑的最遠(yuǎn)。
那么這個(gè)問題如何用編程來實(shí)現(xiàn)呢？我們發(fā)現(xiàn)這是一個(gè)典型的遞推，DP(i, j)表示從坐標(biāo)（i，j）出發(fā)所能滑行的最大長度，且有：DP(i, j)=optimal{DP(i±1, j±1)}+1.
2.3 DP記憶化搜索
dfs(problem a){
if(a has been solved)
then: consult the record.
else//get the optimal solution of problem a.
divide the problem a into several sub-problems(a1,a2,...,ak)
get the solution of problem a by dfs(a1),dfs(a2),...,dfs(ak).
finally write the optimal solution into record.
}
3. 具體實(shí)現(xiàn)
3.1 示例代碼
package cxy.com;
public class LongestIncrementalPath {
static int row;//行
static int colcumn;//列
public static void main(String[] args) {
/**
* [
[9,9,4],
[6,6,8],
[2,1,1]
]
*/
int[][] m = {{9,9,4},{6,6,8},{2,1,1}};//示例
int length = LongestIncrementPath(m);
System.out.println("最長遞增路徑的長度:"+length);
}
public static int LongestIncrementPath(int[][] matrix) {
if(matrix==null||matrix.length==0)return 0;
int max=1;
row=matrix.length;
colcumn=matrix[0].length;
int dpn[][]=new int[row][colcumn];//記錄該點(diǎn)出發(fā)的最長路徑，走過就記錄長度，沒有就是初值==0；
for(int i=0;i<row;i++){//初值：沒走過就是==0；
for(int j=0;j<colcumn;j++){
dpn[i][j]=0;
}
}
for(int i=0;i<row;i++){//以每個(gè)點(diǎn)為起點(diǎn)掃描
for(int j=0;j<colcumn;j++){
int t= longestPath(i,j,matrix,dpn);//方法：以該點(diǎn)出發(fā)的最大長度
if(t>max)max=t;//比較：max記為最大
}
}
return max;
}
static int longestPath(int x,int y,int [][]mat,int dpn[][]){
if(x<0||y<0||x>=row||y>=colcumn)//越界判斷；
return 0;
if(dpn[x][y]!=0)return dpn[x][y];//走過的話，直接取值
int max=0;
//----------向左走
if(y-1>=0 && mat[x][y]<mat[x][y-1]){
int temp;
//走過的話，直接取值
if(dpn[x][y-1]!=0)temp=dpn[x][y-1];
else temp=longestPath(x,y-1,mat,dpn);//遞歸
max=max>temp?max:temp;//記錄最大
}
//----------向右走
if(y+1<colcumn && mat[x][y]<mat[x][y+1]){
int temp;
if(dpn[x][y+1]!=0)temp=dpn[x][y+1];
else temp=longestPath(x,y+1,mat,dpn);
max=max>temp?max:temp;
}
//------------向下走
if(x-1>=0 && mat[x][y]<mat[x-1][y]){
int temp;
if(dpn[x-1][y]!=0)temp=dpn[x-1][y];
else temp=longestPath(x-1,y,mat,dpn);
max=max>temp?max:temp;
}
//------------向上走
if(x+1<row && mat[x][y]<mat[x+1][y]){
int temp;
if(dpn[x+1][y]!=0)temp=dpn[x+1][y];
else temp=longestPath(x+1,y,mat,dpn);
max=max>temp?max:temp;
}
//記為走過了，并存下 以此點(diǎn)出發(fā)的路徑長度
if(dpn[x][y]==0)dpn[x][y]=max+1;
return dpn[x][y];
}
}
3.2 執(zhí)行結(jié)果與分析：
最長遞增路徑的長度:4
2018-5-29
4. 改進(jìn)之路
通過 leetcode 可以看出，執(zhí)行時(shí)間相對(duì)較短，但是內(nèi)存消耗大。參考評(píng)論區(qū)的其他大佬們的思路和答案，可以有另外一種更優(yōu)的解法。
---leetcode 玩家 gyx2110的答案
package cxy.com;
public class LongestIncrementalPath {
static int row;//行
static int colcumn;//列
public static void main(String[] args) {
/**
* [
[9,9,4],
[6,6,8],
[2,1,1]
]
*/
int[][] m = {{9,9,4},{6,6,8},{2,1,1}};//示例
int length =longestIncreasingPath(m);
System.out.println("最長遞增路徑的長度【1】:"+length);
}
public static int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0)
return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int[][] map = new int[m][n];
int res = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = Math.max(res, dfs(matrix, i, j, map, dirs));
}
}
return res;
}
// dfs求以點(diǎn)(i,j)結(jié)尾的最長遞增路徑
public static int dfs(int[][] matrix, int i, int j, int[][] map, int[][] dirs) {
if (map[i][j] != 0)
return map[i][j];
int res = 1;
for (int[] dir : dirs) {
int x = i + dir[0], y = j + dir[1];
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] >= matrix[i][j])
continue;
// 當(dāng)周圍的點(diǎn)小于當(dāng)前點(diǎn)才遞歸
res = Math.max(res, 1 + dfs(matrix, x, y, map, dirs));
}
map[i][j] = res;
return res;
}
}
執(zhí)行結(jié)果與分析：
最長遞增路徑的長度【1】:4
2019-5-29
5. 總結(jié)
記憶化搜索 = 搜索的形式 + 動(dòng)態(tài)規(guī)劃的思想。
