可视化图解算法60：矩阵最长递增路径

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */
func solve(matrix [][]int) int {
  // write code here
  maxMat = newArray(len(matrix), len(matrix[0]))
  maxValue := 0 //最长路径
  for i := 0; i < len(matrix); i++ {
    for j := 0; j < len(matrix[i]); j++ {
      //二维数组中的每一个点都可能是最大路径的起始点
      preMax := dfs(matrix, i, j, -1)
      maxValue = max(maxValue, preMax)
    }
  }
  return maxValue
}
​
var (
  // 如果我们已经知道以该点为头的最长递增路径长度，那么在dfs查找时可以直接使用这个长度，而无需再次计算.
  // 用一个矩阵将已经计算得到的最长递增路径进行存储
  maxMat [][]int
)
​
// 以坐标(i,j)为起始点的最长路径
func dfs(mat [][]int, i int, j int, pre int) int {
  //2.递归终止条件：不是递增，直接返回
  if mat[i][j] <= pre {
    return 0
  }
​
  //3.剪枝：如果该点已经计算过，直接返回，不用再重新计算
  if maxMat[i][j] != 0 {
    return maxMat[i][j]
  }
​
  maxVal := 0
  // 1. 递归步骤
  //1.1 向左
  if i > 0 {
    //用 mat[i][j] 作为 pre，去比较其左侧的数据
    perMax := dfs(mat, i-1, j, mat[i][j])
    maxVal = max(maxVal, perMax)
  }
  //1.2 向右
  if i < len(mat)-1 {
    //用 mat[i][j] 作为 pre，去比较其右侧的数据
    perMax := dfs(mat, i+1, j, mat[i][j])
    maxVal = max(maxVal, perMax)
  }
  //1.3 向上
  if j > 0 {
    //用 mat[i][j] 作为 pre，去比较其上侧的数据
    perMax := dfs(mat, i, j-1, mat[i][j])
    maxVal = max(maxVal, perMax)
  }
  //1.4 向下
  if j < len(mat[i])-1 {
    //用 mat[i][j] 作为 pre，去比较其下侧的数据
    perMax := dfs(mat, i, j+1, mat[i][j])
    maxVal = max(maxVal, perMax)
  }
  maxMat[i][j] = maxVal + 1 //最长路径：上下左右最长的路径+1(当前的点)
  return maxMat[i][j]
}
func max(a, b int) int {
  if a >= b {
    return a
  }
  return b
}
​
func newArray(row, column int) [][]int {
  arr := make([][]int, row)
  for i := 0; i < row; i++ {
    arr[i] = make([]int, column)
  }
  return arr
​
}