最大路径和。给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，只能获得一遍。返回最大路径和。
错误的方法：贪心。左上→右下，取最大值。将走过的路变成零。然后右下→左上，取最大值。最后两个最大值相加。这种方法看起来没问题，实际上是错误的。
正确的方法：递归。两个人都从左上→右下。如果走到同一个位置，值只加一次。如果没走到同一个位置，两个值都加。
时间复杂度：？，不好推断。
空间复杂度：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
}
}执行结果如下：
