2021-07-29：最大路径和。给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出

福大大架构师每日一题

发布于 2021-08-05 16:30:09

7150

发布于 2021-08-05 16:30:09

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-07-29：最大路径和。给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，只能获得一遍。返回最大路径和。

福大大答案2021-07-29：

错误的方法：贪心。左上→右下，取最大值。将走过的路变成零。然后右下→左上，取最大值。最后两个最大值相加。这种方法看起来没问题，实际上是错误的。

正确的方法：递归。两个人都从左上→右下。如果走到同一个位置，值只加一次。如果没走到同一个位置，两个值都加。

时间复杂度：？，不好推断。

空间复杂度：O(N+M)。

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

package main

import "fmt"

func main() {
    grid := [][]int{
        {1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 1, 1, 1, 1, 1},
    }
    ret := cherryPickup(grid)
    fmt.Println(ret)
}

func cherryPickup(grid [][]int) int {
    return process(grid, 0, 0, 0, 0, 0)
}

func process(grid [][]int, a int, b int, c int, d int, ans int) int {
    N := len(grid)
    M := len(grid[0])

    //走到最右下位置
    if a == N-1 && b == M-1 {
        return ans + grid[N-1][M-1]
    }

    temp := 0
    //A下B右
    if a+1 < N && d+1 < M {
        temp = getMax(temp, process(grid, a+1, b, c, d+1, ans))
    }

    //A下B下
    if a+1 < N && c+1 < N {
        temp = getMax(temp, process(grid, a+1, b, c+1, d, ans))
    }

    //A右B右
    if b+1 < M && d+1 < M {
        temp = getMax(temp, process(grid, a, b+1, c, d+1, ans))
    }

    //A右B下
    if b+1 < M && c+1 < N {
        temp = getMax(temp, process(grid, a, b+1, c+1, d, ans))
    }

    if a == c { //同一个位置，只需要加一次
        ans += grid[a][b]
    } else { //不同位置，两个位置都需要加一次
        ans += grid[a][b]
        ans += grid[c][d]
    }

    return ans + temp
}

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

执行结果如下：