https://mp.weixin.qq.com/s/MydL7eyzdfJc6jYZNwFWWw
正幸亏学Go语言,斗胆用Go答题,写了很长:
- //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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |