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

算法——地下城游戏(倒推DP)

[复制链接]
盛夏丨光年丶 发表于 2021-1-2 19:44:20 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
  一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始康健点数为一个正整数。如果他的康健点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去康健点数(若房间里的值为负整数,则表现骑士将损失康健点数);其他房间要么是空的(房间里的值为 0),要么包罗增加骑士康健点数的邪术球(若房间里的值为正整数,则表现骑士将增加康健点数)。
为了尽快到达公主,骑士决定每次只向右或向下移动一步。
leetcode
解题思路:这是一道比力通例的倒推DP问题。


  • 正推的问题在于,有两个重要的参数会影响后续的决定,自身血量和最低血量。也就是说,这样的动态规划是不满足无后效性的。所以,如果接纳倒推,则自身血量就不会影响到后续的决定,因为反面血量再多,也没用。
  • 首先是状态表现,使用一个二维数组表现每个位置到终点的所需的最低血量。
  • 然后是状态转移,取右边和下面两个位置的中的最小值,再减去当前位置的值,就是当前位置所需的最低血量,固然,如果值大于1,那么就将当前效果置为1。
  1. class Solution {    public int calculateMinimumHP(int[][] d) {        int n = d.length, m = d[0].length;        int[][] f = new int[n + 1][m + 1];        for(int i = 0; i = 0; i--) {            for(int j = m - 1; j >= 0; j--) {                int min = Math.min(f[i + 1][j], f[i][j + 1]);                f[i][j] = Math.max(min - d[i][j], 1);            }        }        return f[0][0];    }}
复制代码
来源:https://blog.csdn.net/qq_36263268/article/details/112061140
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

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

本版积分规则


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

18768367769

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

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

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