题解 | #矩阵最长递增路径#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
*/
//DFS+备忘录
func solve( matrix [][]int ) int {
    maxPath = 1
    m := len(matrix)
    n := len(matrix[0]) 
    memo := make([][]int, m)
    for i := 0; i < n; i++ {
        memo[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            maxV := dfs(matrix, i, j, memo)
            maxPath = max(maxPath, maxV)
        }
    }
    return maxPath
}
var maxPath = 1
func dfs(matrix [][]int, i, j int, memo [][]int) int {
    m := len(matrix)
    n := len(matrix[0]) 
    if memo[i][j] != 0 {
        return memo[i][j]
    }
    maxV := 1
    if i-1 > 0 && matrix[i-1][j] > matrix[i][j] {
        maxV = max(maxV, dfs(matrix, i-1, j, memo) + 1)
    }
    if i+1 < m && matrix[i+1][j] > matrix[i][j] {
        maxV = max(maxV, dfs(matrix, i+1, j, memo) + 1)
    }
    if j-1 > 0 && matrix[i][j-1] > matrix[i][j] {
        maxV = max(maxV, dfs(matrix, i, j-1, memo) + 1)
    }
    if j+1 < n && matrix[i][j+1] > matrix[i][j] {
        maxV = max(maxV, dfs(matrix, i, j+1, memo) + 1)
    }
    memo[i][j] = maxV
    return maxV
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}