TalkGo 算法之美第六期

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

func longestIncreasingPath(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = -1
		}
	}

	dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
	var dfs func(x, y int) int
	dfs = func(x, y int) int {
		if dp[x][y] != -1 {
			return dp[x][y]
		}
		dp[x][y] = 1
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m && matrix[x][y] > matrix[xx][yy] {
				dp[x][y] = maxInt(dp[x][y], dfs(xx, yy)+1)
			}
		}
		return dp[x][y]
	}

	ans := 1
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			ans = maxInt(ans, dfs(i, j))
		}
	}
	return ans
}

之前写的了,比较长

func longestIncreasingPath(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	dic := [][2]int{
		{1, 0},
		{0, 1},
		{-1, 0},
		{0, -1},
	}
	ans :=0
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if dp[i][j] != 0 {
			return dp[i][j]
		}
        dp[i][j]=1
		for _, ints := range dic {
			x, y := i+ints[0], j+ints[1]
			if x<0 ||y<0 || x >n-1 || y > m-1 || matrix[x][y] >= matrix[i][j]{
				continue
			}
            temp :=dfs(x,y)
			if temp+1 > dp[i][j]{
				dp[i][j] = temp+1
			}
		}
		if dp[i][j] > ans{
			ans = dp[i][j]
		}
		return dp[i][j]
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
            if dp[i][j] !=0{
                continue
            }
			dfs(i,j)
		}
	}
	return ans
}