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

超过 100% 的 Go 解法

package main

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

	n, m := len(matrix), len(matrix[0])
	var res int

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}

	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	var dfs func(row, col int) int
	dfs = func(row, col int) int {
		if dp[row][col] != 0 {
			return dp[row][col]
		}
		dp[row][col]++

		for _, d := range directions {
			nextRow := row + d[0]
			nextCol := col + d[1]

			if 0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < m && matrix[row][col] < matrix[nextRow][nextCol] {
				temp := dfs(nextRow, nextCol) + 1
				if temp > dp[row][col] {
					dp[row][col] = temp
				}
			}
		}

		return dp[row][col]
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			temp := dfs(i, j)
			if temp > res {
				res = temp
			}
		}
	}

	return res
}