【动态规划算法】第十题:174.地下城游戏

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

【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏
💖作者:小树苗渴望变成参天大树🎈
🎉作者宣言:认真写好每一篇博客💤
🎊作者gitee:gitee✨
💞作者专栏:C语言,数据结构初阶,Linux,C++ 动态规划算法🎄
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏
如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧!


前言

今天我开始讲解动态规划第十题,也是路径问题的最后一个题目,下篇博客博主就一个专题来写一篇博客,不在将相同题型分开写,写在一篇里面也方便大家可以及时对比题目之间的差异,那我们今天讲的这道题有难度,但是理解起来还是不难的,只是细节比较多,我们一起来看看这道题目是怎么样的吧


第十个题目是地下城游戏,这个题目的做法可以参考使用最小花费爬楼梯的解法二来解决此题。
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏
题目解析:
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏
接下来用动态规划的步骤给大家讲解:

  1. 状态表示:经验+题目要求
    按照传统经验,以(i,j)位置为结尾,dp[i][j]表示:从起点到达(i,j)位置的最低健康点数,我们来分析一下
    【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏

以(i,j)位置为结尾的经验就行不通,所以我们得换一种其他的方式


以(i,j)位置为起点,dp[i][j]表示:从(i,j)位置到达终点所需的最低健康点数
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏

  1. 状态转移方程,通过上卖弄的分析已经把状态转移方程写出来了

dp[i][j]=min(dp[i][j+1],dp[i+1][j])-d[i][j];
dp[i][j]=max(1,dp[i][j]);

  1. 初始化:保证数组不越界
    【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏

通过上面的分析:我们只要把dp[m][n-1]=dp[m-1][n]=1;其余位置初始化正无穷就行了

  1. 表顺序,从下往上填每一行,每一行从右往左
  2. 返回值:从起点到终点的最小健康点数,dp[0][0]

代码实现:

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
        int m=d.size(),n=d[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])-d[i][j];
                dp[i][j]=max(1,dp[i][j]);
            }
       return dp[0][0]; 
    }
};

运行结果:
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏

通过这几次的路径问题,我们最重要的是写状态表示,第一步不理解后面的都没有办法做下去,所以多刷题,掌握经验才可以,下篇我讲讲解简单多状态类型的题目,我们下篇再见
【动态规划算法】第十题:174.地下城游戏,动态规划算法,算法,动态规划,游戏文章来源地址https://www.toymoban.com/news/detail-534372.html

到了这里,关于【动态规划算法】第十题:174.地下城游戏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • leetcode做题笔记174. 地下城游戏

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

    2024年02月07日
    浏览(46)
  • 动态规划——地下城游戏

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

    2024年02月11日
    浏览(49)
  • 【学会动态规划】地下城游戏(10)

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

    2024年02月14日
    浏览(63)
  • 【动态规划刷题 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日
    浏览(45)
  • 【动态规划专栏】专题二:路径问题--------6.地下城游戏

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

    2024年02月22日
    浏览(60)
  • 【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61)

    1. 题目解析 题目链接:174. 地下城游戏 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 一、状态表定义 在解决地下城游戏问题时,我们首先需要对状态进行恰当的定义。一个直观的想法是,从起点开始,到达[i, j]位置时所需的最低初始

    2024年04月29日
    浏览(44)
  • 【动态规划上分复盘】这是你熟悉的地下城游戏吗?

    本文讲解关于动态规划思路的两道题目。 1.确定状态表示(确定dp数组的含义) 2.确定状态转移方程(确定dp的递推公式) 3.确定如何初始化(初始化要保证填表正确) 4.确定遍历顺序 5.返回值 点我直达~ 根据题目可知,每一个位置都对应这三种情况: (d[i][j]由题目给出。)

    2024年02月12日
    浏览(43)
  • 【每日易题】Leetcode上Hard难度的动态规划题目——地下城游戏的实现

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,博主最近一直在钻研动态规划算法,最近在Leetcode上刷题的时候遇到一个Hard难度的动态规划题,今天就借此机会来给大家分享一下我对这个题目的一些看法和解题思路(放心,

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

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

    2024年02月04日
    浏览(46)
  • 算法通关第十九关-青铜挑战理解动态规划

    大家好我是苏麟 , 今天聊聊动态规划 . 动态规划是最热门、最重要的算法思想之一,在面试中大量出现,而且题目整体都偏难一些对于大部人来说,最大的问题是不知道动态规划到底是怎么回事。很多人看教程等,都被里面的状态子问题、状态转移方程等等劝退了。 其实,所

    2024年02月03日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包