前言
持续更新了
正文
问题来源
本问题来自leetcode上的329题。
问题描述
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 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]。注意不允许在对角线方向上移动。
分析：
func max(a, b int) int {
if a > b {
return a
}
return b
}
func longestIncreasingPath(matrix [][]int) int {
rowChange := []int{-1,0,1,0}
colChange := []int{0,-1,0,1}
if len(matrix) == 0 {
return 0
}
rl := len(matrix)
cl := len(matrix[0])
memo := make([][]int, rl)
for i := 0; i < rl; i++ {
memo[i] = make([]int, cl)
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if memo[i][j] != 0 {
return memo[i][j]
}
memo[i][j]++
for k := 0; k < 4; k++ {
newRow, newCol := i+rowChange[k], j+colChange[k]
if newRow >= 0 && newRow < rl && newCol >= 0 && newCol < cl && matrix[newRow][newCol] > matrix[i][j] {
memo[i][j] = max(memo[i][j], dfs(newRow, newCol)+1)
}
}
return memo[i][j]
}
m := 0
for i := 0; i < rl; i++ {
for j := 0; j < cl; j++ {
m = max(m, dfs(i,j))
}
}
return m
}
总结：
勤思考。
结语
不管怎么样好好加油。
