【动态规划上分复盘】这是你熟悉的地下城游戏吗?

这篇具有很好参考价值的文章主要介绍了【动态规划上分复盘】这是你熟悉的地下城游戏吗?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

本文讲解关于动态规划思路的两道题目。


一、动态规划五步曲

  • 1.确定状态表示(确定dp数组的含义)
  • 2.确定状态转移方程(确定dp的递推公式)
  • 3.确定如何初始化(初始化要保证填表正确)
  • 4.确定遍历顺序
  • 5.返回值

二、地下城游戏

点我直达~
【动态规划上分复盘】这是你熟悉的地下城游戏吗?,每日挠头算法,动态规划,游戏,算法,leetcode,c++

题目分析

根据题目可知,每一个位置都对应这三种情况:
(d[i][j]由题目给出。)

  • 1.d[i][j] < 0 :该位置有恶魔,骑士打败恶魔会掉血。
  • 2.d[i][j] = 0 :该位置是一条过道,不消耗血量。
  • 3.d[i][j] > 0 :该位置有一个血包,吃了血包可以加血。

我们知道,到达某个位置必须保证骑士血量大于1,否则就算该位置是一个大血包,骑士也享受不到。

思路:动态规划

  • 1.状态表示(确定dp数组的含义)
    每一道dp题的第一点往往是最重要的, 我们需要根据经验+题目要求来确定。
    一般来说,根据经验,确定状态表示有两种:

(1)以[i,j]位置为终点,…
(2)以[i,j]位置为起点,…

写了众多dp题,大部分题型是以[i,j]位置为终点,…,所以我们先看第一种情况:

    • (1)dp[i][j]表示:从起点出发,到达以[i,j]位置为终点时,所需要的最低健康值为dp[i][j].
      那么来看第二步,如何确定递推公式呢?
      请看下图:
      【动态规划上分复盘】这是你熟悉的地下城游戏吗?,每日挠头算法,动态规划,游戏,算法,leetcode,c++
      以该图[i,j]位置为例,到达该位置一定是由上方走来或者左侧走来,所以我们需要考虑上方和左方的两种情况。
      根据题目意思,到达任意一个位置所需要的最低血量最少是1。
      所以我们不仅需要考虑当前位置,还需要考虑上方位置,左方位置,那么到达上方位置又需要进一步考虑,也就是说:到达[i,j]位置需要考虑其之前的所有的位置。并且到达[i,j]位置之后,如果未到达公主所在位置,我们仍然需要考虑后面的位置。并且初始的位置也是题目所要求我们求的,所以这个状态表示行不通。
      来看第二种。
    • (2)dp[i][j]表示:从[i,j]位置出发,到达终点时,所需要的最低健康值为dp[i][j].
      这样就可以行得通了。
      我们只需要考虑它的右方和下方位置即可。
  • 2.状态转移方程(确定递推公式)
    根据状态表示,和题目描述,我们知道[i,j]位置的下一步一定是走到[i+1,j] 或者[i,j+1]位置上的。所以我们应该考虑这三者之间的关系。
    我们知道,骑士到达任意一个位置,要求的最低血量必须大于等于1。
    所以我们从[i,j]位置出发,走到[i+1,j] 或者[i,j+1]位置上之后,在两个位置的任意一个中,血量必须大于等于1。否则就算该位置有大血包,骑士也无法享受。
    那么我们在考虑走到下一步时,应该先考虑自己位置上的值,应该+d[i][j],那么走到下一个位置的话,当前位置的最低健康点数必须大于等于下一个位置的最低健康点数,这样才能保证我们顺利走到下一个位置。
    所以递推公式如下:
    dp[i][j] + d[i][j] >= dp[i+1][j]dp[i][j] + d[i][j] >= dp[i][j+1]
    进行一下移项,得:
    dp[i][j] >= dp[i+1][j] - d[i][j]dp[i][j] >= dp[i][j+1] - d[i][j]
    由于要求最小的健康值,则当等于号成立时,就是最低的健康点数了:
    dp[i][j] = min(dp[i][j+1],dp[i+1][j]) - d[i][j]

但是有一个需要注意的点,当d[i][j]是一个非常大的数时,可能会导致减了d[i][j]之后,dp[i][j]是一个非正整数了,则表示骑士走到[i,j]位置是挂了的状态,并且还能吃了当前位置的血包顺利走到下一个位置,这显然是不符合逻辑的。
所以当dp[i,j]是一个非正整数时,所要求能通过当前位置的最低健康值就是1。
即dp[i][j] = max(1,dp[i][j])

代码如下:

dp[i][j] = min(dp[i-1][j],dp[i][j-1]) - d[i][j];
dp[i][j] = max(1,dp[i][j]);
  • 3.确定如何进行初始化
    上面分析了那么久,我们大概知道当骑士从公主所在位置出发到达公主所在位置时,即:
    【动态规划上分复盘】这是你熟悉的地下城游戏吗?,每日挠头算法,动态规划,游戏,算法,leetcode,c++
    需要知道[i+1,j]位置和[i,j+1]位置。
    所以我们在初始化时,需要多开一行一列的虚拟空间,来更好地进行初始化。具体如下图:
    【动态规划上分复盘】这是你熟悉的地下城游戏吗?,每日挠头算法,动态规划,游戏,算法,leetcode,c++

此时我们需要注意的点是:
虚拟空间的初始化必须保证不能影响正常结果。
在之前写的dp题目中,虚拟空间还需要注意第二点:
下标的映射关系,在这道题中,不需要注意,因为虚拟的空间并没有影响下标。
所以dp[m][n+1] 和dp[m+1][n]位置应该初始化成1,因为走到那个位置,最低健康值必须大于等于1,所以最小值为1。则其他位置根据以往经验,要保证不影响其他值,需要初始化成正无穷大。

  • 4.遍历顺序
    应该从下往上遍历,每行从右往左遍历。

  • 5.返回值
    返回dp[0][0]的值。

具体代码如下

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) 
    {
        //1.确定dp数组的含义
        //dp[i,j]表示:以[i,j]位置为起点,到达终点位置所需要的最小健康点数为dp[i][j]
        
        //2.确定递推公式    
        //dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - d[i][j]
        //但是有可能算出来是非正整数,意味着走到这个位置已经是死了的状态,不符合题目要求。所以如果是非正整数的话,必须最小健康点数为1.
        //dp[i][j] = max(1,dp[i][j]);   
        //3.确定如何初始化
        //由于dp数组的含义是以[i,j]位置为起点的,所以我们必须从终点位置开始初始化,那么应该多开一行一列的虚拟空间来更好地初始化。
        //注意:1.虚拟空间的初始化不能影响结果。
        //这道题不同于之前的题,这里无需再注意下标的映射关系
        //4.遍历顺序(从下到上遍历,每行从右往左遍历)
        //5.返回值
        //dp[0][0]
        int m = d.size();
        int n = d[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[m-1][n] = dp[m][n-1] = 1;

        for(int i = m-1;i>=0;i--)
        {
            for(int j = n-1;j>=0;j--)
            {
                dp[i][j] = min(dp[i][j+1],dp[i+1][j]) - d[i][j];
                //如果dp[i][j] <=0 ,则必须保证到[i,j]位置最低血量为1
                dp[i][j] = max(1,dp[i][j]);
            }
        }

        return dp[0][0];
        //时空复杂度O(m*n)
    }
};

时间复杂度O(m*n),空间复杂度O(m*n)

总结

今天写了一道困难题目,又学到了一种新的dp题型。文章来源地址https://www.toymoban.com/news/detail-524400.html

到了这里,关于【动态规划上分复盘】这是你熟悉的地下城游戏吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【学会动态规划】地下城游戏(10)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:174. 地下城游戏 - 力扣(Lee

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

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

    2024年02月13日
    浏览(42)
  • 【动态规划专栏】专题二:路径问题--------6.地下城游戏

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月22日
    浏览(57)
  • 【动态规划刷题 5】 最小路径和&&地下城游戏

    链接: 64. 最小路径和 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。 示例 2: 输入

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

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

    2024年02月03日
    浏览(46)
  • 【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月04日
    浏览(45)
  • 算法基础复盘笔记Day09【动态规划】—— 背包问题

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月22日
    浏览(46)
  • 算法基础复盘笔记Day10【动态规划】—— 线性DP

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月21日
    浏览(77)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(41)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包