当前位置: 首页 > news >正文

动态规划10:174. 地下城游戏

动态规划解题步骤:

1.确定状态表示:dp[i]是什么

2.确定状态转移方程:dp[i]等于什么

3.初始化:确保状态转移方程不越界

4.确定填表顺序:根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接:174. 地下城游戏 - 力扣(LeetCode)

题解:

本题使用从起点开始到达dp[i][j]位置的方法行不通,因为dp[i][j]不仅被前面的位置影响,还会被后面位置影响

所以本题使用从dp[i][j]位置开始到达终点的方法

1.状态表示:dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数

2.状态转移方程:dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]; if(dp[i][j]<=0) dp[i][j]=1

3.初始化:在右下角多开一行一列,初始化和填表合并(多开位置需要填值:[m][n-1]和[m-1][n]位置填1,其余位置为正无穷)

4.填表顺序:从右下角往左上角填写

5.返回值:dp[0][0]

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {//状态表示//dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数//状态转移方程//dp[i][j]=min(dp[i+1][j]-dungeon[i][j],dp[i][j+1]-dungeon[i][j])//if(dp[i][j]<=0) dp[i][j]=1//创建dp表size_t m=dungeon.size();size_t 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];if(dp[i][j]<=0) dp[i][j]=1;//最低健康值不可能为负数或0,最低为1}}return dp[0][0];}
};

这是使用从起点开始到达dp[i][j]位置的方法,此代码不行

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {//dp[i][j]表示到达dungeon[i][j]所需的最低初始健康点数//if(dungeon[i][j]<0)//dp[i][j]=min(dp[i-1][j]-dungeon[i][j],dp[i][j-1]-dungeon[i][j])//创建dp表size_t m=dungeon.size();size_t n=dungeon[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//多开一行一列dp[0][1]=dp[1][0]=1;//填表for(int i=1;i<m+1;++i){for(int j=1;j<n+1;++j){if(dungeon[i-1][j-1]<0)dp[i][j]=min(dp[i-1][j]-dungeon[i-1][j-1],dp[i][j-1]-dungeon[i-1][j-1]);elsedp[i][j]=min(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
};

相关文章:

动态规划10:174. 地下城游戏

动态规划解题步骤&#xff1a; 1.确定状态表示&#xff1a;dp[i]是什么 2.确定状态转移方程&#xff1a;dp[i]等于什么 3.初始化&#xff1a;确保状态转移方程不越界 4.确定填表顺序&#xff1a;根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接&#xff1a;174.…...

【数据结构】链表-1

数组 数组在分配内存的时候需要先告诉系统它有多大&#xff0c;为什么呢&#xff1f;打个比方&#xff0c;我们有以一列的凳子&#xff0c;按顺序排布&#xff0c;一个位置只放一个&#xff0c;数组呢&#xff0c;是一个家庭&#xff0c;数组这个家庭呢&#xff0c;他们得挨着…...

Python进阶--正则表达式

目录 1. 基础匹配 2. 元字符匹配 1. 基础匹配 正则表达式&#xff0c;又称规则表达式&#xff08;Regular Expression&#xff09;&#xff0c;是使用单个字符串来描述、匹配某个句法规则的字符串&#xff0c;常被用来检索、替换那些符合某个模式&#xff08;规则&#xff…...

富格林:发现潜在欺诈安全交易

富格林指出&#xff0c;在全球经济不确定性加剧的背景下&#xff0c;黄金的避险优势再次吸引了投资者的关注。尤其是在今年&#xff0c;随着多种因素的变化&#xff0c;金价的走势引发了市场的广泛讨论。但事实上黄金与其他投资品类相似&#xff0c;也存在潜在的欺诈套路导致我…...

Linux复习--Linux服务管理类(SSH服务、DHCP+FTP、DNS服务、Apache服务、Nginx服务、HTTP状态码)

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 一、SSH服务 1、问题引出 哪些设置能够提升SSH远程管理的安全等级&#xff1f; 2、SSH的登录验证方式-口令登录 3、SSH的登录验证方式-密钥登录 4、…...

如何用大模型来提升学习效率?

自从2022年底ChatGPT横空出世以来&#xff0c;在过去的十几个月里&#xff0c;生成式人工智能的浪潮席卷并改变着各行各业。 2023年一月&#xff0c;在线课程供应商Study.com曾向1000名18岁以上的学生发起的一项调查显示&#xff0c;当时就已经有超过89%的学生使用ChatGPT来完…...

SQL进阶技巧:如何优雅求解指标累计去重问题?

目录 0 需求概述 1 数据准备 2 问题分析 3 小结 0 需求概述 近期公司开发某项学习功能,改功能有很多学习内容(如java,C,python等方向),每天都会有众多学习用户学习某一项或者多项学习内容。产生数据如下表: 产生数据如下表: 日期 内容 学习用户 2022…...

大数据毕业设计选题推荐-国产电影数据分析-Python数据可视化-Hive-Hadoop-Spark

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

Linux:无法为立即文档创建临时文件: 设备上没有空间

虚拟机磁盘空间不足解决记录 1、问题描述2、问题解决 1、问题描述 在命令行输入命令按Tab键时出现如下报错&#xff1a; 很明显&#xff0c;设备上没有空间&#xff0c;即磁盘空间不足。通过命令查看具体情况如下&#xff1a; df -h2、问题解决 首先想到的是虚拟机扩容。关机虚…...

【SQL】掌握SQL查询技巧:数据筛选与限制

目录 1. DISTINCT&#xff1a;避免重复记录1.1 示意图1.2 使用场景 2. LIMIT&#xff1a;控制查询结果的数量2.1 示意图2.2 使用场景 3. OFFSET&#xff1a;跳过前几行3.1 示意图3.2 使用场景 4. WHERE子句&#xff1a;精细控制数据过滤4.1 示意图4.2 运算符详细说明4.3 基本条…...

大学生社团活动系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;社长管理&#xff0c;社团分类管理&#xff0c;社团信息管理&#xff0c;社团加入管理&#xff0c;社团活动管理&#xff0c;轮播图信息 微信端账号功能包括&#xff1a;系统首页…...

codetop标签双指针题目大全解析(三),双指针刷穿地心!!!!!

复习比学习更重要&#xff0c;更需要投入时间&#xff0c;更需要花费精力 1.字符串的排列2.找出字符串中第一个匹配的下标3.最大连续1的个数II4.数组中的山脉5.移除元素6.两个数组的交集II7.有序数组的平方8.删除有序数组中的重复项II9.寻找重复数10.水果成篮 1.字符串的排列 …...

HarmonyOS应用六之应用程序进阶一

目录&#xff1a; 1、UIAbility的冷启动和UIAbility热启动2、静态资源和动态资源的访问3、页面跳转3.1、页面返回跳转 4、HAR的ArkUI组件、接口、资源&#xff0c;供其他应用或当前应用的其他模块引用4.1、导出HAR的ArkUI组件4.2、引用HAR的ArkUI组件 5、循环渲染6、状态管理最…...

vue开发中变量第一次双向绑定无效,界面并没有变化,第二次则又好了。

这个问题出现的太频繁了,基本大部分用户都遇到这个情况。大部分是弹框的情况。代码如下: <el-dialog:visible.sync="isShowCode" @close="closeCode()"><div class="u4259f"><edite-edite-code isNoShowClose="true"…...

C++基础(8)——string的相关面试题

目录 1.字符串转成整数 2.字符串相加 3.高精度加法模板&#xff08;acwing&#xff09; 4.验证回文串 1.字符串转成整数 题目&#xff1a;将一个字符串转换成一个整数&#xff0c;要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。输入的…...

【Docker】06-DockerCompose

1. Docker compose 2. Docker Compose部署项目 docker-compose.yml version: "3.8"services:mysql:image: mysqlcontainer_name: mysqlports:- "3307:3306"environment:TZ: Asia/ShanghaiMYSQL_ROOT_PASSWORD: 123volumes:- "/root/docker/mysql/…...

代码随想录训练营Day27 | 77. 组合 | 216.组合总和III | 17.电话号码的字母组合

学习文档&#xff1a;代码随想录 (programmercarl.com) 视频链接&#xff1a;代码随想录算法公开课 | 最强算法公开课 | 代码随想录 (programmercarl.com) Leetcode 77. 组合 题目描述 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以…...

Linux文件重定向文件缓冲区

目录 一、C文件接口 二、系统文件I/O 2.1认识系统文件I/O 2.2系统文件I/O 2.3系统调用和库函数 2.4open( )的返回值--文件描述符 2.5访问文件的本质 三、文件重定向 3.1认识文件重定向 3.2文件重定向的本质 3.3在shell中添加重定向功能 3.4stdout和stderr 3.5如何理…...

训练贪吃蛇ai的后续记录

发现可以结合遗传算法的思路&#xff0c;产生更好的效果。 即每训练一段时间&#xff0c;就停下来测试一下新模型的效果。如果效果优于记录中最好的&#xff0c;则继续导入该模型并训练。重复几次&#xff0c;效果可能更好。 例如&#xff0c;昨晚我便通过唯一一个在十次测试中…...

WPF 手撸插件 八 操作数据库一

1、本文将使用SqlSugar创建Sqlite数据库&#xff0c;进行入门的增删改查等操作。擦&#xff0c;咋写着写着凌乱起来了。 SqlSugar官方文档&#xff1a;简单示例&#xff0c;1分钟入门 - SqlSugar 5x - .NET果糖网 2、环境SqlSugar V5.0版本需要.Net Framework 4.6 &#xff0…...

2026整家定制一线品牌选购报告:基于物理指标与国标数据的多维交叉验证

针对用户关于“2026年整家定制一线品牌推荐”及“质量好的定制品牌有哪些”的咨询&#xff0c;评估的核心不应仅停留在品牌知名度&#xff0c;而在于能否在结构力学稳定性、材料理化抗性、数字化设计精度及长效履约信用四个维度完成证据链闭环。本文通过检索 金牌家居&#xff…...

VCAM虚拟摄像头:3大创新功能解锁安卓摄像头的无限应用场景

VCAM虚拟摄像头&#xff1a;3大创新功能解锁安卓摄像头的无限应用场景 【免费下载链接】com.example.vcam 虚拟摄像头 virtual camera 项目地址: https://gitcode.com/gh_mirrors/co/com.example.vcam VCAM虚拟摄像头是一款基于Xposed框架的安卓虚拟相机解决方案&#x…...

告别混乱:我是如何用Hugo + GitHub Actions实现博客自动化构建与发布的

告别混乱&#xff1a;我是如何用Hugo GitHub Actions实现博客自动化构建与发布的 去年我的博客还处于"石器时代"——每次写完文章都要手动执行hugo build&#xff0c;再把public文件夹里的文件拖到服务器。直到某天连续三次忘记更新CNAME文件导致域名解析失败&#…...

RDK X5上800万像素摄像头延迟从7秒降到200ms:我的5个月踩坑与优化实录

RDK X5高分辨率摄像头优化实战&#xff1a;从7秒延迟到200ms的性能飞跃 深夜的显示器前&#xff0c;我盯着屏幕上缓慢刷新的图像——32642448分辨率下&#xff0c;每按一次快门要等待7秒才能看到结果。作为一名在嵌入式视觉领域摸爬滚打多年的开发者&#xff0c;这种性能表现简…...

vLLM-v0.17.1效果展示:128K上下文下PagedAttention稳定性验证

vLLM-v0.17.1效果展示&#xff1a;128K上下文下PagedAttention稳定性验证 1. vLLM框架核心能力 vLLM是一个专为大语言模型推理优化的高性能服务库&#xff0c;最新发布的v0.17.1版本在超长上下文处理能力上实现了重大突破。这个最初由加州大学伯克利分校开发的框架&#xff0…...

深度拆解 JDK1.8 ConcurrentHashMap 核心方法:从 put 到扩容,彻底吃透并发神器

在 Java 高并发编程中&#xff0c;ConcurrentHashMap是线程安全 Map 的绝对首选&#xff0c;而 JDK1.8 版本对它的重构堪称并发设计的巅峰之作 —— 彻底抛弃分段锁&#xff0c;用CAS 桶级 synchronized实现极致细粒度并发&#xff0c;搭配多线程协同扩容、链表红黑树转换、高…...

3分钟掌握Windows音频路由:让每个程序都有专属音频输出 [特殊字符]

3分钟掌握Windows音频路由&#xff1a;让每个程序都有专属音频输出 &#x1f3a7; 【免费下载链接】audio-router Routes audio from programs to different audio devices. 项目地址: https://gitcode.com/gh_mirrors/au/audio-router 你是否曾经遇到过这样的烦恼&…...

AD7606模数转换器的FPGA驱动设计与实现(串行/并行双模式解析)

1. AD7606模数转换器核心特性解析 AD7606这颗16位模数转换芯片在工业现场堪称"数据捕手"&#xff0c;我经手过的电力监控、振动分析项目中都能看到它的身影。与普通ADC不同&#xff0c;它最吸引工程师的特性是双模数据输出——就像高速公路的ETC和人工通道可以并行运…...

经典游戏无法运行?DDrawCompat让老游戏在新系统重生

经典游戏无法运行&#xff1f;DDrawCompat让老游戏在新系统重生 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_mirrors/dd/DDrawCom…...

解向量前33位是DG位置,后33位是无功补偿容量

3.基于遗传算法的配电网优化配置 主要内容&#xff1a;分布式电源、无功补偿装置接入配电网&#xff0c;考虑配电网经济性和电能质量为目标函数&#xff0c;使用遗传算法进行优化配置&#xff0c;在IEEE33节点&#xff0c;118节点系统进行了仿真验证。 文件夹内运行main函数。配…...