请选择 进入手机版 | 继续访问电脑版

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

[复制链接]
冰宇 发表于 2021-1-1 18:31:41 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )