dp算法 力扣174地下城游戏

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

在学习编程时,算法是一道硬菜,而dp作为算法的一份子,它的地位在编程界举足轻重。

174. 地下城游戏 - 力扣(LeetCode)

本文是Java代码哦~

一、题目详情

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

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

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

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

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

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

示例 1:
输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

dp算法 力扣174地下城游戏,java,算法,leetcode
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。

示例 2:

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

提示:

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

二、题目解析

对于dp算法题,一般有两种解题思路:

1、dp[i][j]表示,从[i][j]位置开始,到终点所需最低初始健康点数;

2、dp[i][j]表示,从[0][0]位置开始,到[i][j]所需最低初始健康点数.

由题意可知,第二种解题思路不适合该题目。

在不考虑越界问题情况下,

  1. 对于[i][j]位置,它的下一步是[i][j+1] 或者 [i+1][j].
  2. 设[i][j]位置所需最低初始健康点数为dp[i][j], dp[i][j]+dungeon[i][j] >= dp[i][j+1] 以及 dp[i][j]+dungeon[i][j] >= dp[i+1][j]
  3. 故 dp[i][j] >= dp[i+1][j] - dungeon[i][j] 或 dp[i][j] >= dp[i][j+1] - dungeon[i][j]

当dungeon[i][j]足够大时,即使 dp[i][j]+dungeon[i][j] 满足血量要求,我们也需要考虑骑士到达[i][j]位置前,血量足够存活,故需要将 dp[i][j] 与 1 取一个最大值:dp[i][j] = ,Math.max(1, dp[i][j]);

考虑越界问题时,可以增加虚拟结点帮助解题,如:

dp算法 力扣174地下城游戏,java,算法,leetcode

 填表顺序是从下往上,从右往左,故需考虑虚拟节点存储值大小。我们只需要保证终点结点计算时是使用虚拟结点,其他结点不使用虚拟结点,故将虚拟节点中,影响终点的结点置为1,其余结点置为无穷大。

dp算法 力扣174地下城游戏,java,算法,leetcode

 最后返回dp[0][0]即可。

三、代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        //1.创建dp表
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        //2.初始化
        for(int i=0; i<=m; i++){
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j=0; j<=n; j++){
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m][n-1] = dp[m-1][n] = 1;
        //3.填表
        for(int i=m-1; i>=0;i--){
            for(int j=n-1; j>=0; j--){
                dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j],1);
            }
        }
        //返回值
        return dp[0][0];
    }
}

提交截图:

dp算法 力扣174地下城游戏,java,算法,leetcode

 

结语

这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!文章来源地址https://www.toymoban.com/news/detail-560350.html

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

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

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

相关文章

  • 174-地下城游戏

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

    2024年02月11日
    浏览(42)
  • LeetCode刷题--- 地下城游戏

    个人主页: 元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题   【C++】     ​​​​​​ 数据结构与算法  ​​​ 前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的   我讲述题目会把讲解部分分为3个部分: 1、

    2024年01月18日
    浏览(41)
  • 【leetcode热题】 地下城游戏

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

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

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

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

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

    2024年02月05日
    浏览(45)
  • dp算法 力扣978、力扣139、力扣467

    目录 一、力扣978978. 最长湍流子数组 - 力扣(LeetCode) (一)题目详情 (二)算法讲解 (三)代码 二、力扣139139. 单词拆分 - 力扣(LeetCode) (一)题目详情 (二)算法讲解 (三)代码 三、力扣467467. 环绕字符串中唯一的子字符串 - 力扣(LeetCode) (一)题目详情 (二)

    2024年02月16日
    浏览(31)
  • dp算法 力扣152乘积最大子数组

    本文是Java代码!! 152. 乘积最大子数组 - 力扣(LeetCode) 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入

    2024年02月13日
    浏览(40)
  • dp算法 力扣309最佳买卖股票时机含冷冻期

    给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意:你不能同时参与多笔交

    2024年02月14日
    浏览(39)
  • LeetCode(力扣)45. 跳跃游戏 IIPython

    https://leetcode.cn/problems/jump-game-ii/description/

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

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

    2024年02月11日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包