func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func longestIncreasingPath(matrix [][]int) int {
n, m := len(matrix), len(matrix[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
dp[i][j] = -1
}
}
dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
var dfs func(x, y int) int
dfs = func(x, y int) int {
if dp[x][y] != -1 {
return dp[x][y]
}
dp[x][y] = 1
for i := 0; i < 4; i++ {
xx, yy := x+dx[i], y+dy[i]
if xx >= 0 && xx < n && yy >= 0 && yy < m && matrix[x][y] > matrix[xx][yy] {
dp[x][y] = maxInt(dp[x][y], dfs(xx, yy)+1)
}
}
return dp[x][y]
}
ans := 1
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
ans = maxInt(ans, dfs(i, j))
}
}
return ans
}
之前写的了，比较长
func longestIncreasingPath(matrix [][]int) int {
n, m := len(matrix), len(matrix[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
dic := [][2]int{
{1, 0},
{0, 1},
{-1, 0},
{0, -1},
}
ans :=0
var dfs func(i, j int) int
dfs = func(i, j int) int {
if dp[i][j] != 0 {
return dp[i][j]
}
dp[i][j]=1
for _, ints := range dic {
x, y := i+ints[0], j+ints[1]
if x<0 ||y<0 || x >n-1 || y > m-1 || matrix[x][y] >= matrix[i][j]{
continue
}
temp :=dfs(x,y)
if temp+1 > dp[i][j]{
dp[i][j] = temp+1
}
}
if dp[i][j] > ans{
ans = dp[i][j]
}
return dp[i][j]
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if dp[i][j] !=0{
continue
}
dfs(i,j)
}
}
return ans
}