2021-05-06：给定一个二维数组matrix， 你可以从任何位置出发，走向上下左右四个方向 。返回能走出来的最长的

2021-05-06：给定一个二维数组matrix， 你可以从任何位置出发，走向上下左右四个方向 。返回能走出来的最长的递增链长度。

福大大 答案2021-05-06：

自然智慧即可。
动态规划。二维数组的所有位置，每个位置上下左右全部试一次。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    matrix := [][]int{{1, 2, 3}, {6, 5, 4}}
    ret := 0

    ret = longestIncreasingPath1(matrix)
    fmt.Println(ret)

    ret = longestIncreasingPath2(matrix)
    fmt.Println(ret)
}
func longestIncreasingPath1(matrix [][]int) int {
    ans := 0
    N := len(matrix)
    M := len(matrix[0])
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            ans = getMax(ans, process1(matrix, i, j))
        }
    }
    return ans
}

// 从m[i][j]开始走，走出来的最长递增链，返回！
func process1(m [][]int, i int, j int) int {
    up := 0
    if i > 0 && m[i][j] < m[i-1][j] {
        up = process1(m, i-1, j)
    }
    down := 0
    if i < (len(m)-1) && m[i][j] < m[i+1][j] {
        down = process1(m, i+1, j)
    }

    left := 0
    if j > 0 && m[i][j] < m[i][j-1] {
        left = process1(m, i, j-1)
    }
    right := 0
    if j < (len(m[0])-1) && m[i][j] < m[i][j+1] {
        right = process1(m, i, j+1)
    }
    return getMax(getMax(up, down), getMax(left, right)) + 1
}

func longestIncreasingPath2(matrix [][]int) int {
    ans := 0
    N := len(matrix)
    M := len(matrix[0])
    dp := make([][]int, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]int, M)
    }
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            ans = getMax(ans, process2(matrix, i, j, dp))
        }
    }
    return ans
}

// 从m[i][j]开始走，走出来的最长递增链，返回！
func process2(m [][]int, i int, j int, dp [][]int) int {
    //fmt.Println("i=", i, ",j=", j)
    if dp[i][j] != 0 {
        return dp[i][j]
    }
    // (i,j)不越界
    up := 0
    if i > 0 && m[i][j] < m[i-1][j] {
        process2(m, i-1, j, dp)
    }

    down := 0
    if i < (len(m)-1) && m[i][j] < m[i+1][j] {
        down = process2(m, i+1, j, dp)
    }

    left := 0
    if j > 0 && m[i][j] < m[i][j-1] {
        left = process2(m, i, j-1, dp)
    }

    right := 0
    if j < (len(m[0])-1) && m[i][j] < m[i][j+1] {
        right = process2(m, i, j+1, dp)
    }

    ans := getMax(getMax(up, down), getMax(left, right)) + 1
    dp[i][j] = ans
    return ans
}

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

执行结果如下：

左神java代码