【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析

本文主要是介绍【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划

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

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

174. 地下城游戏

题目解析

状态表示

我们可以定义,dp[i][j]表示从(i,j)位置出发,到达右下角所需的最小生命值。

状态的表示通常是经验+题目来得到的。

经验指的是,以某个位置为结尾,或者以某个位置开始。

这道题目我们选择以(i,j)位置开始到达最后的思路定义状态。

故状态表示为,dp[i][j]表示从(i,j)位置出发,到达右下角所需的最小生命值。

为什么选择这一种方式而不选择从(0,0)位置开始到达(i,j)位置所需的最小生命值?

上图所示,如果我们考虑蓝色和绿色两种路径,

绿色路径「从出发点到当前点的路径和」为 1,「从出发点到当前点所需的最小初始值」为 3。

蓝色路径「从出发点到当前点的路径和」为 −1,「从出发点到当前点所需的最小初始值」为 2。

我们希望「从出发点到当前点的路径和」尽可能大,而「从出发点到当前点所需的最小初始值」尽可能小。这两条路径各有优劣。

在上图中,我们知道应该选取绿色路径,因为蓝色路径的路径和太小,使得蓝色路径需要增大初始值到 4 才能走到终点,而绿色路径只要 3 点初始值就可以直接走到终点。但是如果把终点的 −2 换为 0,蓝色路径只需要初始值 2,绿色路径仍然需要初始值 3,最优决策就变成蓝色路径了。

因此,如果按照从左上往右下的顺序进行动态规划,我们无法直接确定到达 (1,2) 的方案,因为有两个重要程度相同的参数同时影响后续的决策。也就是说,这样的动态规划是不满足「无后效性」的。

于是我们考虑从右下往左上进行动态规划。令 dp[i][j] 表示从坐标 (i,j) 到终点所需的最小初始值。换句话说,当我们到达坐标 (i,j)时,如果此时我们的路径和不小于 dp[i][j],我们就能到达终点。

这是leetcode官方题解中的部分解析。

我们可以得出,如果用以某位置为结尾思路定义状态表示,我们没办法依靠前面的状态准确推导出(i,j)位置的状态,而后续的数据依旧会影响(i,j)位置的状态值,所以这种方式是错误的。在运用动态规划时,必须满足【无后效性】,所以我们选择以某位置开始思路定义状态表示。

当我们选择 以某位置开始思路定义状态表示时,我们前面的状态值并不会影响后面的状态值,可以保证满足【无后效性】,所以这种方式是可以行的。

故状态表示为,dp[i][j]表示从(i,j)位置出发,到达右下角所需的最小生命值。

状态转移方程

我们考虑,(i,j)位置的值能不能由其他的状态值推导得出,dp[i+1][j]表示从(i+1,j)位置出发,到达右下角所需的最小生命值。dp[i][j+1]表示从(i,j+1)位置出发,到达右下角所需的最小生命值。对于(i,j)的状态值,分两种情况,(i,j)房间内的值是正数或者是负数。如果(i,j)房间的值是负数,说明我们到达(i,j)时的最小生命值应该是min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]。如果(i,j)房间的值是正数,说明我们到达(i,j)时的最小生命值应该是min(dp[i][j+1],dp[i+1][j])-dungeon[i][j],但是这样写又会有两种情况,那就是减出来的数是大于零的数或者是小于等于零的数,我们到达(i,j)房间时最小生命不可能是小于等于零的数,而减出来的数是小于等于零意义是,(i,j)的血包特别的大,即使你的血是负数,吃完之后都可以到达终点,所以实际上到达该位置的生命值为最低的1就可以。

故状态转移方程为,

dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]

if(dp[i][j]<=0)dp[i][j]=1

初始化

根据状态转移方程,我们如果要推导出(i,j)位置的状态,就需要运用到(i+1,j)和(i,j+1)位置的状态,所以我们为了不越界,需要初始化最后一行和最后一列的数据。我们发现这种初始化有点复杂,所以我们把对这些位置的初始化转化为对虚拟节点的初始化,也就是创建虚拟节点代替原先初始化的位置。

对于红色位置的状态,他们所需访问的虚拟节点的值,是一定不能取到的,根据状态转移方程,

dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]

if(dp[i][j]<=0)dp[i][j]=1

所以他们访问的虚拟节点值应该置正无穷,这样取最小就不会取到。

对于紫色位置的状态,他的状态值应该是1-dungeon[i][j]所以min(dp[i+1][j],dp[i][j+1])的值应该为1。所有我们可以先把所有位置置正无穷,然后在这两个位置选一个位置置1就可以了。

填表顺序

从右到左,从下到上

返回值

返回dp[0][0]

代码实现

 
int calculateMinimumHP(int** dungeon, int dungeonSize, int* dungeonColSize) {int row=dungeonSize;int col=dungeonColSize[0];int dp[row+1][col+1];for(int i=0;i<=row;i++){memset(dp[i],0x3f,sizeof(dp[i]));}dp[row-1][col]=1;for(int i=row-1;i>=0;i--){for(int j=col-1;j>=0;j--){dp[i][j]=fmin(dp[i][j+1],dp[i+1][j])-dungeon[i][j];if(dp[i][j]<=0) dp[i][j]=1;}}return dp[0][0];
}
 
    for(int i=0;i<=row;i++){memset(dp[i],0x3f,sizeof(dp[i]));}

void *memset(void *s, int ch, size_t n);

函数解释:将s中前n个字节 (typedef unsigned int size_t )用 ch 替换并返回 s 。

memset:作用是在一段内存块中填充某个给定的值,它是对较大的结构体数组进行清零操作的一种最快方法。

_itoa可以把x值转化为char类型的2进制数存放在string中。

我们发现x的二进制数是00111111 00111111 00111111 00111111。

用_itoa转换二进制数时,前导零省略了,实际上是00111111 00111111 00111111 00111111。

一个int类型占4个字节。

一个字节占8位二进制数。

而0x3f的二进制数是00111111。

memset的意思是,将x中前n个字节,用0x3f最后一个字节对应的二进制数替换。

那为什么要赋值0x3f:

作为无穷大使用

因为4个字节均为0x3f时,0x3f3f3f3f的十进制是1061109567,也就是10^ 9级别的(和0x7fffffff一个数量级),而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。

可以保证无穷大加无穷大仍然不会超限。

另一方面,由于一般的数据都不会大于10^9,所以当我们把无穷大加上一个数据时,它并不会溢出(这就满足了“无穷大加一个有穷的数依然是无穷大”),事实上0x3f3f3f3f+0x3f3f3f3f=2122219134,这非常大但却没有超过32-bit int的表示范围,所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。

面试题 17.16. 按摩师

题目解析

状态表示

我们可以定义dp[i]表示,从nums[0]开始一直到nums[i],选择不相邻的预约情况中,最长的时间数。

状态转移方程

我们想一想dp[i]能不能由其他的状态推导得出。

dp[i]表示,从nums[0]开始一直到nums[i],选择不相邻的预约情况中,最长的时间数。

dp[i-1]表示,从nums[0]开始一直到nums[i-1],选择不相邻的预约情况中,最长的时间数。

dp[i-2]表示,从nums[0]开始一直到nums[i-2],选择不相邻的预约情况中,最长的时间数。

如果i位置预约我们选择,那么i-1位置预约肯定不选择,这种情况对应的最长时间数就是

dp[i-2]+nums[i]

如果i位置预约我们不选择,这种情况对应的最长时间数就是

dp[i-1]

因为我们存储是最长时间数,所以需要从两种情况中选一个时间更长的。

故状态转移方程为,dp[i]=max(dp[i-2]+nums[i],dp[i-1])

初始化

根据状态转移方程,我们推导出i位置的状态需要用到(i-2)和(i-1)的状态值。

我们想要统一所有需要得到的状态,都通过状态转移方程推导得出,那么我们就需要创建虚拟节点替代需要初始化的位置。

创建虚拟节点有几点注意事项,

第一,对虚拟节点的初始化必须保证后续的推导过程不出错。

第二,注意下标映射关系的变化,也就是状态表示和状态转移方程的下标变换。

状态转移方程为,dp[i]=max(dp[i-2]+nums[i-2],dp[i-1])。

对于紫色第一个状态值,应该是填自己的时间数,所以需要选择dp[i-2]+nums[i-2]且dp[n-2]需要为零,即dp[0]为0。

对于紫色第二个状态值,要么是填自己的值,要么填紫色第一个状态值。

所以dp[i-2]为零,即dp[1]。

故初始化为dp[0]=dp[1]=0。

填表顺序

从左往右

返回值

放回最后一个元素的值,dp[n+1]

n是nums的数组大小

代码实现

 

int massage(int* nums, int numsSize){int n=numsSize;int dp[n+2];memset(dp,0,sizeof(dp));for(int i=2;i<=n+1;i++){dp[i]=fmax(dp[i-2]+nums[i-2],dp[i-1]);}return dp[n+1];
}

213. 打家劫舍 II

题目解析

我们可以把问题分成两种情况,要么数组的长度大于1,要么数组的长度等于1。

当数组的长度大于1时,我们有两种情况。

第一,我们考虑第一个房子,不考虑最后一个房子。

第二,我们不考虑第一个房子,考虑最后一个房子。

这样问题就转化为普通的不环绕的问题了。

当数组的长度等于1时,我们只能选择nums[0],这一个房子。

所以我们只需要解决不环绕的问题即可。

状态表示

我们可以定义dp[i]表示从nums[0]开始到nums[i]这些房子,选择不相邻房子方法数中金额最大的金额数。

状态转移方程

我们想一想dp[i]能不能由其他状态推导得出。

dp[i]表示从nums[0]开始到nums[i]这些房子,选择不相邻房子方法数中金额最大的金额数。

dp[i-1]表示从nums[0]开始到nums[i-1]这些房子,选择不相邻房子方法数中金额最大的金额数。

dp[i-2]表示从nums[0]开始到nums[i-2]这些房子,选择不相邻房子方法数中金额最大的金额数。

对dp[i]这个状态进行分析,如果该房子选择的话,i-1房子就不能选择,所以这种情况下金额最大数为dp[i-2]+nums[i]

如果该房子不选择的话,最大金额数就是dp[i-1]

故状态转移方程为,dp[i]=max(dp[i-2]+nums[i],dp[i-1])

初始化

根据状态转移方程,我们推导出i位置的状态需要用到(i-2)和(i-1)的状态值。

我们想要统一所有需要得到的状态,都通过状态转移方程推导得出,那么我们就需要创建虚拟节点替代需要初始化的位置。

创建虚拟节点有几点注意事项,

第一,对虚拟节点的初始化必须保证后续的推导过程不出错。

第二,注意下标映射关系的变化,也就是状态表示和状态转移方程的下标变换。

状态转移方程为,dp[i]=max(dp[i-2]+nums[i-2],dp[i-1])。

对于紫色第一个状态值,应该是填自己的时间数,所以需要选择dp[i-2]+nums[i-2]且dp[n-2]需要为零,即dp[0]为0。

对于紫色第二个状态值,要么是填自己的值,要么填紫色第一个状态值。

所以dp[i-2]为零,即dp[1]。

故初始化为dp[0]=dp[1]=0。

填表顺序

从左往右

返回值

分两种情况,计算当长度大于1时,考虑第一个房子而不考虑最后一个房子的金额数,

和当长度大于1时,不考虑第一个房子而考虑最后一个房子的金额数。

和当长度为1时,nums[0]的金额数

返回三者中最大的金额数即可。

代码实现

 
int rob_(int* nums,int numsSize, int left,int right) {int n=numsSize;int dp[n+2];memset(dp,0,sizeof(dp));for(int i=left;i<=right;i++){dp[i]=fmax(dp[i-2]+nums[i-2],dp[i-1]);}return dp[right];
}
int rob(int* nums,int numsSize){int num1=rob_(nums,numsSize,2,numsSize);int num2=rob_(nums,numsSize,3,numsSize+1);return fmax(fmax(num1,num2),nums[0]);
}

我们rob_函数就是解决不环绕的一列房子问题。

接着把环绕的问题转化为不环绕的问题。

如果数组的长度大于1。

如果我们考虑第一个房子,而不考虑最后一个房子,只需要填写dp表中下标2到下标numsSize状态的推导填写。

如果我们不考虑第一个房子,而考虑最后一个房子,只需要填写dp表中下标3到下标numsSize+1的状态的推导填写。

如果数组的长度等于1。

考虑nums[0]的金额数。

如果数组长度为1,num1和num2计算出来的值都是零,因为numsSize 为1,而循环是从下标2开始或者从下标3开始,所以最后的返回值是初始化的零。

此时只需要返回nums[0]即可,nums [0]一定大于0。

所以返回比较num1,num2和nums[0]即可。

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/531403

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五):Blender锥桶建模

前言 本系列教程旨在使用UE5配置一个具备激光雷达+深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础,Nav2相关的学习教程可以参考本人的其他博客Nav2代价地图实现和原理–Nav2源码解读之CostMap2D(上)-CSDN博客往期教程: 第一期:基于UE5和ROS2的激光雷达+深度RG