动态规划|【路径问题】|174.地下城游戏

题目

174. 地下城游戏

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

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

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

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

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

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

示例 1:

输入: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

代码

int min(int a,int b)
{
    return (a<=b)?a:b;
}
int max(int a,int b)
{
    return (a>b)?a:b;
}
int calculateMinimumHP(int** dungeon, int dungeonSize, int* dungeonColSize) 
{

    int dp[202][202]={0};
    int n=dungeonColSize[0];
    int m=dungeonSize;
    for(int i=0;i<202;i++)
    {
        for(int j=0;j<202;j++)
        {
            dp[i][j]=INT_MAX;
        }
    }

    dp[m-1][n]= dp[m][n-1]=1;
   
   
    
    //[i,j]以i,j位置为起点到达终点所需的最小点数
    //那么为什么不能用i,j位置为结尾从起点到达所需的最小点数,因为这个位置不仅受前面影响也是受后面的影响的
    for(int i=m-1;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {
            //分两种情况,
            //从i,j位置往右走,假设dp i,j位置里面是x,x既要能走过原来的也要能走要下一个因此x=dp[i][j+1]-dungeon[i][j]
            //从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-1][j-1]很大dp[i][j]会变成负的,
            //dungeon[i-1][j-1],很大就是说就算过来的是负值也可以走到结尾,但是过来不能是负的,最小也要是1
            dp[i][j]=max(1,dp[i][j]);
        }

    }

    return dp[0][0];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/446679.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

map和set(二)——AVL树的简单实现

引入 二叉搜索树有其自身的缺陷&#xff0c;假如往树中 插入的元素有序或者接近有序&#xff0c;二叉搜索树就会退化成单支树&#xff0c;时间复杂度会退化成O(N)&#xff0c;因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理&#xff0c;即采用平衡树来实现。简…

可免费使用的AI平台汇总 + 常用赋能科研的AI工具推荐

赋能科研&#xff0c;AI工具助你飞跃学术巅峰&#xff01;(推荐收藏) 文章目录 赋能科研&#xff0c;AI工具助你飞跃学术巅峰&#xff01;(推荐收藏)一、可免费使用的AI平台汇总1. ChatGPT2. New Bing3. Slack4. POE5. Vercel6. 其他平台7. 特定功能平台8. 学术资源平台9. 中文…

14 OpenCv边缘处理

文章目录 卷积边界问题边缘处理copyMakeBorder 算子代码 卷积边界问题 图像卷积的时候边界像素&#xff0c;不能被卷积操作&#xff0c;原因在于边界像素没有完全跟kernel重叠&#xff0c;所以当3x3滤波时候有1个像素的边缘没有被处理&#xff0c;5x5滤波的时候有2个像素的边缘…

华为OD机试C卷“跳步-数组”Java解答

描述 示例 算法思路1 不断移动数组将元素删去&#xff08;并未彻底删除&#xff0c;而是将数字元素前移实现“伪删除”&#xff09;这样删除元素的位置就呈现一定规律&#xff0c;详细见下图&#xff08;潦草的画&#xff09; 答案1 import java.util.*;public class Main {…

蓝桥杯刷题5--GCD和LCM

目录 1. GCD 1.1 性质 1.2 代码实现 2. LCM 2.1 代码实现 3. 习题 3.1 等差数列 3.2 Hankson的趣味题 3.3 最大比例 3.4 GCD 1. GCD 整数a和b的最大公约数是能同时整除a和b的最大整数&#xff0c;记为gcd(a, b) 1.1 性质 GCD有关的题目一般会考核GCD的性质。   …

国家医保局开通异地就医备案办理功能,哪些人群适用?

2022年6月30日&#xff0c;国家医保局会同财政部印发《关于进一步做好跨省异地就医基本医疗保险直接结算工作的通知》&#xff08;民保发〔2022〕30号&#xff09;。 22号文&#xff08;以下简称《通知》&#xff09;。 《通知》明确&#xff0c;长期跨省异地居住或临时跨省外出…

PostgreSQL数据优化——死元组清理

最近遇到一个奇怪的问题&#xff0c;一个百万级的PostgreSQL表&#xff0c;只有3个索引。但是每次执行insert或update语句就要几百ms以上。经过查询发现是一个狠简单的问题&#xff0c;数据库表死元组太多了&#xff0c;需要手动清理。 在 PG 中&#xff0c;update/delete 语句…

Axure原型设计项目效果 全国职业院校技能大赛物联网应用开发赛项项目原型设计题目

目录 前言 一、2022年任务书3效果图 二、2022年任务书5效果图 三、2022年国赛正式赛卷 四、2023年国赛第一套样题 五、2023年国赛第二套样题 六、2023年国赛第三套样题 七、2023年国赛第四套样题 八、2023年国赛第七套样题 九、2023年国赛正式赛题&#xff08;第八套…

点赞功能真的有必要上 Redis 吗?(Mongo、MySQL、Redis、MQ 实测性能对比)

目录 一、你会怎么设计一个点赞功能&#xff1f; 1.1、点赞实现思路 1.2、点赞功能设计 1.2.1、MySQL 单表 1.2.2、单表 MySQL 关联表 1.2.3、MySQL 关联表 mq 1.2.4、redis mq 1.2.5、mongodb 关联文档 二、性能测试 2.1、前置说明 2.2、10 万数据准备 一、你会…

PyTorch完整的神经网络模型训练(使用GPU训练)

1.什么是CUDA&#xff1a; CUDA&#xff08;Compute Unified Device Architecture&#xff09;是由NVIDIA开发的一种并行计算平台和编程模型。它允许开发者在NVIDIA GPU上进行通用目的的并行计算&#xff0c;包括深度学习、科学计算、图形处理和加密等任务。 CUDA通过提供一组…

vulhub中Weblogic WLS Core Components 反序列化命令执行漏洞复现(CVE-2018-2628)

Oracle 2018年4月补丁中&#xff0c;修复了Weblogic Server WLS Core Components中出现的一个反序列化漏洞&#xff08;CVE-2018-2628&#xff09;&#xff0c;该漏洞通过t3协议触发&#xff0c;可导致未授权的用户在远程服务器执行任意命令。 访问http://your-ip:7001/consol…

人工智能:探索智慧的未来

目录 前言1 人工智能的简介1.1 人工智能的定义1.2 任务范围1.3 模拟人类认知 2 人工智能发展2.1 起步阶段2.2 发展阶段2.3 繁荣阶段 3 弱人工智能和强人工智能3.1 弱人工智能&#xff08;ANI&#xff09;3.2 强人工智能&#xff08;AGI&#xff09; 4 人工智能主要技术4.1 机器…

【C++11】包装器和bind

文章目录 一. 为什么要有包装器&#xff1f;二. 什么是包装器&#xff1f;三. 包装器的使用四. bind 函数模板1. 为什么要有 bind &#xff1f;2. 什么是 bind ?3. bind 的使用场景 一. 为什么要有包装器&#xff1f; function 包装器&#xff0c;也叫作适配器。C 中的 funct…

Elastic Stack--06--JavaAPI----索引(创建-查询- 删除)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 环境准备添加依赖&#xff1a;HelloElasticsearch JavaAPI-索引1.创建2.查询3.删除 环境准备 添加依赖&#xff1a; <dependencies><dependency><g…

第G3周:CGAN入门|生成手势图像

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 一、前置知识 CGAN&#xff08;条件生成对抗网络&#xff09;的原理是在原始GAN的基础上&#xff0c;为生成器和判别器提供 额外的条件信息…

vue3 ref获取子组件显示 __v_skip : true 获取不到组件的方法 怎么回事怎么解决

看代码 问题出现了 当我想要获取这个组件上的方法时 为什么获取不到这个组件上的方法呢 原來&#xff1a; __v_skip: true 是 Vue 3 中的一个特殊属性&#xff0c;用于跳过某些组件的渲染。当一个组件被标记为 __v_skip: true 时&#xff0c;Vue 将不会对该组件进行渲染&am…

ABAP接口-RFC连接(ABAP TO ABAP)

目录 ABAP接口-RFC连接&#xff08;ABAP TO ABAP&#xff09;创建ABAP连接RFC函数的调用 ABAP接口-RFC连接&#xff08;ABAP TO ABAP&#xff09; 创建ABAP连接 事务代码&#xff1a;SM59 点击创建&#xff0c;填写目标名称&#xff0c;选择连接类型&#xff1a; 填写主机名…

打卡--MySQL8.0 一(单机部署)

一路走来&#xff0c;所有遇到的人&#xff0c;帮助过我的、伤害过我的都是朋友&#xff0c;没有一个是敌人。如有侵权&#xff0c;请留言&#xff0c;我及时删除&#xff01; MySQL 8.0 简介 MySQL 8.0与5.7的区别主要体现在&#xff1a;1、性能提升&#xff1b;2、新的默认…

02-app端文章查看,静态化freemarker,分布式文件系统minIO

app端文章查看&#xff0c;静态化freemarker,分布式文件系统minIO 1)文章列表加载 1.1)需求分析 文章布局展示 1.2)表结构分析 ap_article 文章基本信息表 ap_article_config 文章配置表 ap_article_content 文章内容表 三张表关系分析 1.3)导入文章数据库 1.3.1)导入数据…

【vue.js】文档解读【day 2】 | 响应式基础

如果阅读有疑问的话&#xff0c;欢迎评论或私信&#xff01;&#xff01; 本人会很热心的阐述自己的想法&#xff01;谢谢&#xff01;&#xff01;&#xff01; 文章目录 响应式基础声明响应式状态(属性)响应式代理 vs 原始值声明方法深层响应性DOM 更新时机有状态方法 响应式…