2021-05-25：给定一个矩阵matrix，值有正、负、0，蛇可以空降到最左列的任何一个位置，初始增长值是0，蛇每一步可以选择右上、右、右下三个方向的任何一个前进，沿途的数字累加起来，作为增长值；但是蛇一旦增长值为负数，就会死去 。蛇有一种能力，可以使用一次：把某个格子里的数变成相反数，蛇可以走到任何格子的时候停止。返回蛇能获得的最大增长值。
福大大 答案2021-05-25：
动态规划。
代码用golang编写。代码如下：
代码语言：txt复制package main
import (
"fmt"
"math"
)
func main() {
matrix := [][]int{
{1, 2, 3, 4},
{-5, 6, -7, 8}}
ret := walk2(matrix)
fmt.Println(ret)
}
func walk2(matrix [][]int) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
max := math.MinInt64
dp := make([][][]int, len(matrix))
for i := 0; i < len(matrix); i {
dp[i] = make([][]int, len(matrix[0]))
for j := 0; j < len(matrix[0]); j {
dp[i][j] = make([]int, 2)
}
}
for i := 0; i < len(dp); i {
dp[i][0][0] = matrix[i][0]
dp[i][0][1] = -matrix[i][0]
max = getMax(max, getMax(dp[i][0][0], dp[i][0][1]))
}
for j := 1; j < len(matrix[0]); j {
for i := 0; i < len(matrix); i {
preUnuse := dp[i][j-1][0]
preUse := dp[i][j-1][1]
if i-1 >= 0 {
preUnuse = getMax(preUnuse, dp[i-1][j-1][0])
preUse = getMax(preUse, dp[i-1][j-1][1])
}
if i 1 < len(matrix) {
preUnuse = getMax(preUnuse, dp[i 1][j-1][0])
preUse = getMax(preUse, dp[i 1][j-1][1])
}
dp[i][j][0] = -1
dp[i][j][1] = -1
if preUnuse >= 0 {
dp[i][j][0] = matrix[i][j] preUnuse
dp[i][j][1] = -matrix[i][j] preUnuse
}
if preUse >= 0 {
dp[i][j][1] = getMax(dp[i][j][1], matrix[i][j] preUse)
}
max = getMax(max, getMax(dp[i][j][0], dp[i][j][1]))
}
}
return max
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
图片左神java代码
