题解 | 矩阵最长递增路径

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
*/
func solve( matrix [][]int ) int {
    // write code here

    h := len(matrix)
    w := len(matrix[0])
    path := make([][]int, h)
    for i:=0; i<h; i++{
        path[i] = make([]int, w)
    }
    var res int
    for i:=0; i<h; i++{
        for j:=0; j<w; j++{
            path[i][j] = dfs(matrix, path, i, j)
            res = max(path[i][j], res)
        }
    }

    return res
}

func dfs(matrix, path [][]int, i, j int) int {
    h := len(matrix)
    w := len(matrix[0])

    if path[i][j] != 0{
        return path[i][j]
    }

    res := 1

    if i>0 && matrix[i-1][j] > matrix[i][j] {
        res = max(dfs(matrix, path, i-1, j)+1, res)
    }

    if j>0 && matrix[i][j-1] > matrix[i][j] {
        res = max(dfs(matrix, path, i, j-1)+1, res)
    }

    if i<h-1 && matrix[i+1][j] > matrix[i][j] {
        res = max(dfs(matrix, path, i+1, j)+1 , res)
    }

    if j<w-1 && matrix[i][j+1] > matrix[i][j] {
        res = max(dfs(matrix, path, i, j+1)+1, res)
    }

    path[i][j] = res
    return res
}

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