leetcode 174地下城游戏 动态规划解法的Go语言实现 原创

https://mp.weixin.qq.com/s/MydL7eyzdfJc6jYZNwFWWw
正幸亏学Go语言，斗胆用Go答题，写了很长：

1. //20201231FHP：动态规划魔塔问题package mainimport "fmt"func init() {}func main() {        var nRow int = 3        var nCol int = 3        var dp = make([][][]int, nRow, nRow)        for i := 0; i < nRow; i++ {                dp[i] = make([][]int, nCol, nCol)                for j := 0; j < nCol; j++ {                        dp[i][j] = make([]int, 2, 2)                        dp[i][j] = []int{-1, -1} //使用缓存                        //dp[i][j][0]：到达[i][j]所需的最小开局血量                        //dp[i][j][1]：以最小开局血量到达[i][j]时的当前血量，残血                }        }        // var grid [][]int        grid := make([][]int, nRow, nRow)        for i := 0; i < nRow; i++ {                grid[i] = make([]int, nCol, nCol)        }        grid[0] = []int{-5, 30, 10}        grid[1] = []int{1, -10, -5}        grid[2] = []int{3, -3, -2}        // grid[0] = []int{-5, 0, 0}        // grid[1] = []int{10, -100, 0}        // grid[2] = []int{0, 0, 0}        // grid[0] = []int{0, -1, -1}        // grid[1] = []int{100, 0, 0}        // grid[2] = []int{20, -10, 0}        // grid[0] = []int{0, 0}        // grid[1] = []int{0, 0}        minBlood, _ := DP(grid, 0, 0, dp)        fmt.Printf("%d\n", minBlood)}//DP 计算dp[i][j]并返回dp[i][j][0]func DP(grid [][]int, i, j int, dp [][][]int) (int, int) {        if dp[i][j][0] != -1 { //使用缓存                return dp[i][j][0], dp[i][j][1]        }        var nRow int = len(grid)        var nCol int = len(grid[0])        if i == nRow-1 && j == nCol-1 {                if grid[i][j] > 0 {                        dp[i][j][0] = 1 //到达某个网格后先查抄血量再举行加减血，所以不能落地成盒                        dp[i][j][1] = 1 + grid[i][j]                        return dp[i][j][0], dp[i][j][1]                } else {                        dp[i][j][0] = -1*grid[i][j] + 1                        dp[i][j][1] = 1                        return dp[i][j][0], dp[i][j][1]                }        }        if i == nRow-1 {                //只能从左边过来                dp[i][j+1][0], dp[i][j+1][1] = DP(grid, i, j+1, dp)                res := dp[i][j+1][1] + grid[i][j]                if res > 0 { //左边的最小初血满意                        dp[i][j][0] = dp[i][j+1][0]                        dp[i][j][1] = res                        return dp[i][j][0], dp[i][j][1]                } else { //按照左边的最小初血不敷，差-res+1                        dp[i][j][0] = dp[i][j+1][0] - res + 1                        dp[i][j][1] = 1                        return dp[i][j][0], dp[i][j][1]                }        }        if j == nCol-1 {                //只能从上面下来                dp[i+1][j][0], dp[i+1][j][1] = DP(grid, i+1, j, dp)                res := dp[i+1][j][1] + grid[i][j]                if res > 0 {                        dp[i][j][0] = dp[i+1][j][0]                        dp[i][j][1] = res                        return dp[i][j][0], dp[i][j][1]                } else { //在dp[i+1][j][0]的初血的根本上增加到至少到当前格的血量为1                        dp[i][j][0] = dp[i+1][j][0] - res + 1                        dp[i][j][1] = 1                        return dp[i][j][0], dp[i][j][1]                }        }        //从上、左网格到达当前网格，观察需要的最小初血        var minBloodUp int        var minBloodLeft int        //从上面过来：        dp[i+1][j][0], dp[i+1][j][1] = DP(grid, i+1, j, dp)        resup := dp[i+1][j][1] + grid[i][j]        if resup > 0 {                minBloodUp = dp[i+1][j][0]        } else {                minBloodUp = dp[i+1][j][0] - resup + 1        }        //从左边过来：        dp[i][j+1][0], dp[i][j+1][1] = DP(grid, i, j+1, dp)        resleft := dp[i][j+1][1] + grid[i][j]        if resleft > 0 {                minBloodLeft = dp[i][j+1][0]        } else {                minBloodLeft = dp[i][j+1][0] - resleft + 1        }        if minBloodUp  0 {                        dp[i][j][1] = resup                } else {                        dp[i][j][1] = 1                }        } else {                // dp[i][j+1][0], dp[i][j+1][1] = DP(grid, i, j+1, dp)                dp[i][j][0] = minBloodLeft                if resleft > 0 {                        dp[i][j][1] = resleft                } else {                        dp[i][j][1] = 1                }        }        return dp[i][j][0], dp[i][j][1]}

复制代码

 

来源：https://blog.csdn.net/HayPinF/article/details/112055181
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！