给定一个二维数组matrix， 你可以从任何位置出发，走向上下左右四个方向 。返回能走出来的最长的递增链长度。
自然智慧即可。
动态规划。二维数组的所有位置，每个位置上下左右全部试一次。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
matrix := [][]int{{1, 2, 3}, {6, 5, 4}}
ret := 0
ret = longestIncreasingPath1(matrix)
fmt.Println(ret)
ret = longestIncreasingPath2(matrix)
fmt.Println(ret)
}
func longestIncreasingPath1(matrix [][]int) int {
ans := 0
N := len(matrix)
M := len(matrix[0])
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
ans = getMax(ans, process1(matrix, i, j))
}
}
return ans
}
// 从m[i][j]开始走，走出来的最长递增链，返回！
func process1(m [][]int, i int, j int) int {
up := 0
if i > 0 && m[i][j] < m[i-1][j] {
up = process1(m, i-1, j)
}
down := 0
if i < (len(m)-1) && m[i][j] < m[i+1][j] {
down = process1(m, i+1, j)
}
left := 0
if j > 0 && m[i][j] < m[i][j-1] {
left = process1(m, i, j-1)
}
right := 0
if j < (len(m[0])-1) && m[i][j] < m[i][j+1] {
right = process1(m, i, j+1)
}
return getMax(getMax(up, down), getMax(left, right)) + 1
}
func longestIncreasingPath2(matrix [][]int) int {
ans := 0
N := len(matrix)
M := len(matrix[0])
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
ans = getMax(ans, process2(matrix, i, j, dp))
}
}
return ans
}
// 从m[i][j]开始走，走出来的最长递增链，返回！
func process2(m [][]int, i int, j int, dp [][]int) int {
//fmt.Println("i=", i, ",j=", j)
if dp[i][j] != 0 {
return dp[i][j]
}
// (i,j)不越界
up := 0
if i > 0 && m[i][j] < m[i-1][j] {
process2(m, i-1, j, dp)
}
down := 0
if i < (len(m)-1) && m[i][j] < m[i+1][j] {
down = process2(m, i+1, j, dp)
}
left := 0
if j > 0 && m[i][j] < m[i][j-1] {
left = process2(m, i, j-1, dp)
}
right := 0
if j < (len(m[0])-1) && m[i][j] < m[i][j+1] {
right = process2(m, i, j+1, dp)
}
ans := getMax(getMax(up, down), getMax(left, right)) + 1
dp[i][j] = ans
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
