?？途W(wǎng): BM61
求矩陣的最長遞增路徑
解題思路:
1. 遍歷二維矩陣每個位置，max求出所有位置分別為終點時的最長路徑
2. 求某個位置為終點的最長路徑時，使用動態(tài)規(guī)劃dp對已經(jīng)計算出的位置進行記錄
3. 處理某個位置的最長路徑時，如果dp[i][j]位置已有值，則直接返回即可，否則對此位置賦值1，再對上下左右4個方向進行遞歸求解，每次遞歸后返回的最長路徑需+1才是當(dāng)前位置的最長路徑，使用max選擇最大值賦予dp[i][j]，4個方向均遍歷完后返回dp[i][j]給主程序。文章來源：http://www.zghlxwxcb.cn/news/detail-730617.html
代碼:文章來源地址http://www.zghlxwxcb.cn/news/detail-730617.html
// go
package main
// import "fmt"
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
* 遞增路徑的最大長度
* @param matrix int整型二維數(shù)組 描述矩陣的每個數(shù)
* @return int整型
*/
func max(x, y int) int {
if x > y {return x} else {return y}
}
var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func process(matrix, dp [][]int, i, j, m, n int) int {
if dp[i][j] > 0 {
return dp[i][j]
}
dp[i][j] = 1
for k := 0; k < 4; k++ {
nexti := i + dirs[k][0]
nextj := j + dirs[k][1]
if nexti >= 0 && nexti < m && nextj >= 0 && nextj < n && matrix[nexti][nextj] < matrix[i][j] {
dp[i][j] = max(dp[i][j], process(matrix, dp, nexti, nextj, m, n) + 1)
}
}
return dp[i][j]
}
func solve( matrix [][]int ) int {
// write code here
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
m := len(matrix)
n := len(matrix[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
res := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
res = max(res, process(matrix, dp, i, j, m, n))
}
}
return res
}
到了這里，關(guān)于算法 矩陣最長遞增路徑-(遞歸回溯+動態(tài)規(guī)劃)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
