2021-05-25：给定一个矩阵matrix，值有正、负、

原创

福大大架构师每日一题

修改于 2021-05-26 10:01:31

3090

2021-05-25：给定一个矩阵matrix，值有正、负、0，蛇可以空降到最左列的任何一个位置，初始增长值是0，蛇每一步可以选择右上、右、右下三个方向的任何一个前进，沿途的数字累加起来，作为增长值；但是蛇一旦增长值为负数，就会死去。蛇有一种能力，可以使用一次：把某个格子里的数变成相反数，蛇可以走到任何格子的时候停止。返回蛇能获得的最大增长值。

福大大答案2021-05-25：

动态规划。

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

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
    }
}

执行结果如下：