动态规划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. 地下城游戏
动态规划解题步骤: 1.确定状态表示:dp[i]是什么 2.确定状态转移方程:dp[i]等于什么 3.初始化:确保状态转移方程不越界 4.确定填表顺序:根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接:174.…...
【数据结构】链表-1
数组 数组在分配内存的时候需要先告诉系统它有多大,为什么呢?打个比方,我们有以一列的凳子,按顺序排布,一个位置只放一个,数组呢,是一个家庭,数组这个家庭呢,他们得挨着…...
Python进阶--正则表达式
目录 1. 基础匹配 2. 元字符匹配 1. 基础匹配 正则表达式,又称规则表达式(Regular Expression),是使用单个字符串来描述、匹配某个句法规则的字符串,常被用来检索、替换那些符合某个模式(规则ÿ…...
富格林:发现潜在欺诈安全交易
富格林指出,在全球经济不确定性加剧的背景下,黄金的避险优势再次吸引了投资者的关注。尤其是在今年,随着多种因素的变化,金价的走势引发了市场的广泛讨论。但事实上黄金与其他投资品类相似,也存在潜在的欺诈套路导致我…...
Linux复习--Linux服务管理类(SSH服务、DHCP+FTP、DNS服务、Apache服务、Nginx服务、HTTP状态码)
前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 一、SSH服务 1、问题引出 哪些设置能够提升SSH远程管理的安全等级? 2、SSH的登录验证方式-口令登录 3、SSH的登录验证方式-密钥登录 4、…...
如何用大模型来提升学习效率?
自从2022年底ChatGPT横空出世以来,在过去的十几个月里,生成式人工智能的浪潮席卷并改变着各行各业。 2023年一月,在线课程供应商Study.com曾向1000名18岁以上的学生发起的一项调查显示,当时就已经有超过89%的学生使用ChatGPT来完…...
SQL进阶技巧:如何优雅求解指标累计去重问题?
目录 0 需求概述 1 数据准备 2 问题分析 3 小结 0 需求概述 近期公司开发某项学习功能,改功能有很多学习内容(如java,C,python等方向),每天都会有众多学习用户学习某一项或者多项学习内容。产生数据如下表: 产生数据如下表: 日期 内容 学习用户 2022…...
大数据毕业设计选题推荐-国产电影数据分析-Python数据可视化-Hive-Hadoop-Spark
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
Linux:无法为立即文档创建临时文件: 设备上没有空间
虚拟机磁盘空间不足解决记录 1、问题描述2、问题解决 1、问题描述 在命令行输入命令按Tab键时出现如下报错: 很明显,设备上没有空间,即磁盘空间不足。通过命令查看具体情况如下: df -h2、问题解决 首先想到的是虚拟机扩容。关机虚…...
【SQL】掌握SQL查询技巧:数据筛选与限制
目录 1. DISTINCT:避免重复记录1.1 示意图1.2 使用场景 2. LIMIT:控制查询结果的数量2.1 示意图2.2 使用场景 3. OFFSET:跳过前几行3.1 示意图3.2 使用场景 4. WHERE子句:精细控制数据过滤4.1 示意图4.2 运算符详细说明4.3 基本条…...
大学生社团活动系统小程序的设计
管理员账户功能包括:系统首页,个人中心,学生管理,社长管理,社团分类管理,社团信息管理,社团加入管理,社团活动管理,轮播图信息 微信端账号功能包括:系统首页…...
codetop标签双指针题目大全解析(三),双指针刷穿地心!!!!!
复习比学习更重要,更需要投入时间,更需要花费精力 1.字符串的排列2.找出字符串中第一个匹配的下标3.最大连续1的个数II4.数组中的山脉5.移除元素6.两个数组的交集II7.有序数组的平方8.删除有序数组中的重复项II9.寻找重复数10.水果成篮 1.字符串的排列 …...
HarmonyOS应用六之应用程序进阶一
目录: 1、UIAbility的冷启动和UIAbility热启动2、静态资源和动态资源的访问3、页面跳转3.1、页面返回跳转 4、HAR的ArkUI组件、接口、资源,供其他应用或当前应用的其他模块引用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.高精度加法模板(acwing) 4.验证回文串 1.字符串转成整数 题目:将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。数值为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.电话号码的字母组合
学习文档:代码随想录 (programmercarl.com) 视频链接:代码随想录算法公开课 | 最强算法公开课 | 代码随想录 (programmercarl.com) Leetcode 77. 组合 题目描述 给定两个整数 n 和 k,返回范围 [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的后续记录
发现可以结合遗传算法的思路,产生更好的效果。 即每训练一段时间,就停下来测试一下新模型的效果。如果效果优于记录中最好的,则继续导入该模型并训练。重复几次,效果可能更好。 例如,昨晚我便通过唯一一个在十次测试中…...
WPF 手撸插件 八 操作数据库一
1、本文将使用SqlSugar创建Sqlite数据库,进行入门的增删改查等操作。擦,咋写着写着凌乱起来了。 SqlSugar官方文档:简单示例,1分钟入门 - SqlSugar 5x - .NET果糖网 2、环境SqlSugar V5.0版本需要.Net Framework 4.6 ࿰…...
熵值法实战避坑指南:从数据标准化到权重计算,新手最容易踩的3个雷
熵值法实战避坑指南:从数据标准化到权重计算,新手最容易踩的3个雷 第一次用熵值法做综合评价时,我盯着屏幕上几乎相同的权重值发愣——这和教科书上"差异越大权重越高"的描述完全不符。直到深夜排查才发现,原来在数据标…...
JEECG Boot项目实战:如何优雅地移除登录验证码(前后端完整操作指南)
JEECG Boot项目实战:如何优雅地移除登录验证码(前后端完整操作指南) 在JEECG Boot的开发过程中,验证码功能虽然能有效防止恶意登录,但在某些特定场景下反而会成为效率瓶颈。想象一下这样的场景:开发团队正在…...
深入解析iOS中CUICatalog: Invalid asset name警告的解决方案与优化实践
1. 理解CUICatalog: Invalid asset name警告的本质 当你正在调试iOS应用时,突然在控制台看到一堆[framework] CUICatalog: Invalid asset name supplied: 的警告信息,这感觉就像开车时仪表盘突然亮起故障灯。作为开发者,我们首先需要理解这个…...
WebSocket消息压缩终极指南:如何平衡性能与带宽的完整实践
WebSocket消息压缩终极指南:如何平衡性能与带宽的完整实践 【免费下载链接】async-http-client Asynchronous Http and WebSocket Client library for Java 项目地址: https://gitcode.com/gh_mirrors/as/async-http-client 在现代实时应用中,We…...
付费墙绕过工具深度解析:技术原理与合规使用指南
付费墙绕过工具深度解析:技术原理与合规使用指南 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字内容付费模式日益普及的今天,如何在尊重知识产权的前提…...
3天刷完2026最新Java高频面试题(1000 道附答案解析)
2026年金三银四一半儿快要过去了,总结了上半年各类 Java 面试题,初中级和中高级都有,包括 Java 基础,JVM 知识面试题库,开源框架面试题库,操作系统面试题库,多线程面试题库,Tcp 面试…...
重塑前端图片处理流程:compressorjs的高效压缩技术突破之路
重塑前端图片处理流程:compressorjs的高效压缩技术突破之路 【免费下载链接】compressorjs compressorjs: 是一个JavaScript图像压缩库,使用浏览器原生的canvas.toBlob API进行图像压缩。 项目地址: https://gitcode.com/gh_mirrors/co/compressorjs …...
探索视频采集技术:OBS Studio实现高效直播录制的创新方法
探索视频采集技术:OBS Studio实现高效直播录制的创新方法 【免费下载链接】obs-studio OBS Studio - 用于直播和屏幕录制的免费开源软件。 项目地址: https://gitcode.com/GitHub_Trending/ob/obs-studio 在当今内容创作领域,视频采集技术是直播与…...
ThinkPad 4G/5G 连网不支持 IPv6?一文教你判断与设置
很多用 ThinkPad 内置 4G/5G 模块上网的用户,在使用 IPv6 相关服务、测速或网络诊断时,会发现自己明明设备很新,却始终无法获取 IPv6 地址,甚至误以为电脑硬件不支持。尤其在办公、远程、云服务等场景,IPv6 支持与否直…...
如何通过SpacetimeGaussians实现实时动态视图合成:从安装到应用全指南
如何通过SpacetimeGaussians实现实时动态视图合成:从安装到应用全指南 【免费下载链接】SpacetimeGaussians [CVPR 2024] Spacetime Gaussian Feature Splatting for Real-Time Dynamic View Synthesis 项目地址: https://gitcode.com/gh_mirrors/sp/SpacetimeGau…...
