2021-07-29：最大路径和。给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，只能获得一遍。返回最大路径和。
福大大 答案2021-07-29：
错误的方法：贪心。左上→右下，取最大值。将走过的路变成零。然后右下→左上，取最大值。最后两个最大值相加。这种方法看起来没问题，实际上是错误的。
正确的方法：递归。两个人都从左上→右下。如果走到同一个位置，值只加一次。如果没走到同一个位置，两个值都加。
时间复杂度：？，不好推断。
空间复杂度：O(N M)。
代码用golang编写。代码如下：
代码语言：txt复制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
}
}执行结果如下：
在这里插入图片描述左神java代码
牛客网原题
