LeetCode刷题--- 地下城游戏

这篇具有很好参考价值的文章主要介绍了LeetCode刷题--- 地下城游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 

【C++】    

​​​​​​

数据结构与算法

 ​​​


前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


地下城游戏

题目链接:地下城游戏

题目

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1:

LeetCode刷题--- 地下城游戏,力扣动态规划算法题,leetcode,游戏,算法

输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。

示例 2:

输入:dungeon = [[0]]
输出:1

提示:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

解法

算法原理讲解

我们这题使用动态规划,我们做这类题目可以分为以下五个步骤文章来源地址https://www.toymoban.com/news/detail-802322.html

  1. 状态显示
  2. 状态转移方程
  3. 初始化(防止填表时不越界)
  4. 填表顺序
  5. 返回值
  • 状态显示
  1. 这道题如果我们和以前的题目一样定义成:从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数。 那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
  2. 这个时候我们要换⼀种状态表示:从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。 综上所述,定义状态表示为: dp[i][j] 表示:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。
  • 状态转移方程
对于 dp[i][j] ,从 [i, j] 位置出发,下⼀步会有两种选择(为了⽅便理解,设 dp[ i ][ j ] 的最终答案是 x
  • 走到右边,然后⾛向终点 。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要大于等于右边位 置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i][j + 1] 。 通过移项可得: x >= dp[i][j + 1] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j]
  • ⾛到下边,然后⾛向终点。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于下边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i + 1][j] 。 通过移项可得: x >= dp[i + 1][j] - dungeon[i][j] 。因为我们要的是最小值,因此这种情况下的 x = dp[i + 1][j] -dungeon[i][j]
综上所述,我们需要的是两种情况下的最⼩值,因此可得状态转移⽅程为:
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
但是,如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话, dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 ,那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话,说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最⼤值即可: dp[i][j] = max(1, dp[i][j])。
  • 初始化(防止填表时不越界)
dp 表最后⾯添加⼀⾏,并且添加⼀列后,所有的值都先初始化为⽆穷⼤,然后让 dp[m][n - 1] = dp[m - 1][n] = 1 即可。
  • 填表顺序
根据「状态转移⽅程」,我们需要「从下往上填每⼀⾏」,「每⼀⾏从右往左」。
  • 返回值
根据「状态表⽰」,我们需要返回 dp[0][0] 的值。

代码实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int m = dungeon.size();
        int n = dungeon[0].size();

        vector<vector<int>> dp(m+1, vector<int>(n+1,INT_MAX));
        // 初始化
        dp[m][n-1] = dp[m-1][n] = 1;
        // 填表
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >=0; j--)
            {
                dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = max(1,dp[i][j]);     // 防止正数太大
            }
        }

        return dp[0][0];
    }
};

到了这里,关于LeetCode刷题--- 地下城游戏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode热题】 地下城游戏

    恶魔们抓住了公主并将她关在了地下城  dungeon  的  右下角  。地下城是由  m x n  个房间组成的二维网格。我们英勇的骑士最初被安置在  左上角  的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻

    2024年03月20日
    浏览(34)
  • leetcode做题笔记174. 地下城游戏

    恶魔们抓住了公主并将她关在了地下城  dungeon  的  右下角  。地下城是由  m x n  个房间组成的二维网格。我们英勇的骑士最初被安置在  左上角  的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻

    2024年02月07日
    浏览(47)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(59)
  • 【leetcode刷题之路】初级算法(2)——链表+树+排序和搜索+动态规划

    3.1 【链表】删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/ 给出的就是要删除的那个节点,直接前后移动就行了。 3.2 【双指针】删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 利用双指针left和right,首先让right遍历n个节点,再让两

    2024年02月10日
    浏览(51)
  • 【算法】动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法分析 | 代码示例 )

    LeetCode 55. 跳跃游戏 : https://leetcode.cn/problems/jump-game/ 给定一个 非负整数数组 nums ,你最初位于数组的 第一个下标 0 位置 。 数组中的每个元素 代表你在该位置可以 跳跃的最大长度。 判断你 是否能够到达最后一个下标。 给定一个一维数组 , 数组元素不能有负数 , 如 : {2, 2,

    2024年02月10日
    浏览(39)
  • 【动态规划算法】第十题:174.地下城游戏

    💖作者:小树苗渴望变成参天大树🎈 🎉作者宣言:认真写好每一篇博客💤 🎊作者gitee:gitee✨ 💞作者专栏:C语言,数据结构初阶,Linux,C++ 动态规划算法🎄 如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧! 今天我开始讲解动态规划第十题,也是路径问题的最后一

    2024年02月13日
    浏览(45)
  • 【动态规划】【 矩阵】【逆向思考】C++算法174地下城游戏

    视频算法专题 动态规划汇总 矩阵 逆向思考 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数

    2024年02月03日
    浏览(46)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(46)
  • 【LeetCode】动态规划 刷题训练(六)

    点击查看:买卖股票的最佳时机 III 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入:p

    2024年02月11日
    浏览(29)
  • 【LeetCode】动态规划 刷题训练(九)

    点击查看:467. 环绕字符串中唯一的子字符串 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

    2024年02月15日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包