Day41 | 动态规划 :完全背包应用 完全平方数单词拆分(类比爬楼梯)

Day41 | 动态规划 :完全背包应用 完全平方数&&单词拆分(类比爬楼梯)

动态规划应该如何学习?-CSDN博客

01背包模板 | 学习总结-CSDN博客

完全背包模板总结-CSDN博客

难点:

代码都不难写,如何想到完全背包并把具体问题抽象为完全背包才是关键

文章目录

  • Day41 | 动态规划 :完全背包应用 完全平方数&&单词拆分(类比爬楼梯)
    • 279.完全平方数
      • 思路分析:
      • 1.回溯法
      • 2.记忆化搜索
      • 3.动态规划
      • 4.滚动数组
    • 139.单词拆分(类比爬楼梯)
      • 思路分析:
        • 类比爬楼梯
        • 而本题中呢
        • 难理解的点:||dp[i]的作用
      • 1.回溯法
      • 2.记忆化搜索
      • 3. 1:1翻译为动态规划

279.完全平方数

279. 完全平方数 - 力扣(LeetCode)

思路分析:

dfs(i,c)的含义是从前i个数里面选,能凑够容量c的完全平方数的最少数量

直观想法:

n是背包的容量,物品就是1到n这些数字

w重量数组为{1,2,3,4…n}。由于根号n*根号n=n,我们加的时候还是加的这些数字的平方数而不是它本身,所以w其实就是{1,2,3…根号n}到根号n就行了,后面的数平方一下肯定比n大,也没必要加了

v价值数组全都为1,因为选一个数只能给数量加1

那就和322. 零钱兑换 - 力扣(LeetCode)一模一样了

只是那道题w是硬币的面值,而这道题是1-n这些数字本身的数值

笔者这么理解就可以写出来了,看了题解后,其实w数组更加清晰的说是:完全平方数才是他们本身的重量

{1,4,9,16,25…}这样的吗,上面的{1,2,3,4}这些可以看做是序号i,{1,4,9,16}是序号i对应的完全平方数i*i

把 1,4,9,16,⋯ 这些完全平方数视作物品重量,物品价值都是 1。由于每个数(物品)选的次数没有限制,所以本题是一道标准的完全背包问题

和零钱兑换一样,就是选或不选i²的问题

dp[i][c]=min(dp[i-1][c],dp[i][c-i*i]);

image-20241109155109879

1.回溯法

1.参数和返回值

c是背包容量,本题是前i个数的完全平方数i²要凑成的数

i是物品编号,本题的物品编号i的完全平方数就是我们的物品,所以有这两个参数就够了

int dfs(int i,int c)

2.终止条件

i等于0,说明已经没有数可以选了,我们dfs的含义是前i个数凑成c,所以0和0前面已经没有数字了

此时如果要凑成的数c是0,说明我们找到了合法的方案,返回0(因为求的是物品的个数而不是凑成的方案数量,方案数量的话返回的就是1)

否则的话说明当前的分支不是合法的方法,返回正无穷(int最大值除以2是为了防止返回值+1操作溢出)

		if(i==0)if(c==0)return 0;elsereturn INT_MAX/2;

3.本层逻辑

如果说要凑的数c已经比i²小了,那就是不选i,继续往下递归,看能不能放上i-1

如果比i²大,那就在选或不选中挑一个最小值进行返回

		if(c<i*i)return dfs(i-1,c);return min(dfs(i-1,c),dfs(i,c-i*i)+1);

完整代码:

我们传入的时候物品编号从根号n开始就好,因为要凑成n,而根号n*根号n=n,比根号n大的数的平方一定比n大

当然是超时的

class Solution {
public:int dfs(int i,int c){if(i==0)if(c==0)return 0;elsereturn INT_MAX/2;if(c<i*i)return dfs(i-1,c);return min(dfs(i-1,c),dfs(i,c-i*i)+1);}int numSquares(int n) {return dfs(sqrt(n),n);}
};

2.记忆化搜索

就是还是全都初始化为-1,每次返回前给dp赋值,碰到不是-1的那就是算过的,那就直接返回计算过的结果,不需要再次递归了

完整代码:

class Solution {
public:int dfs(int i,int c,vector<vector<int>>& dp){if(i==0)if(c==0)return 0;elsereturn INT_MAX;if(dp[i][c]!=-1)return dp[i][c];if(c<i*i)return dp[i][c]=dfs(i-1,c,dp);return dp[i][c]=min(dfs(i-1,c,dp),dfs(i,c-i*i,dp)+1);}int numSquares(int n) {vector<vector<int>> dp(sqrt(n)+1,vector<int>(n+1,-1));return dfs(sqrt(n),n,dp);}
};

3.动态规划

1.确定dp数组以及下标的含义

dp[i][j]前i个数的完全平方数i²凑成j的最少方案数量

i是物品编号

j是当前要凑的数(背包容量)

2.确定递推公式

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

3.dp数组如何初始化

在回溯中,递归终止条件是i==0&&c==0,返回0

那就是dp[0][0]就是0,其他的都是正无穷(INT_MAX/2)

4.确定遍历顺序

和完全背包一样,先遍历物品在遍历容量,从前往后遍历

完整代码:

class Solution {
public:int numSquares(int n) {vector<vector<unsigned>> dp(sqrt(n)+1,vector<unsigned>(n+1,INT_MAX/2));dp[0][0]=0;for(int i=1;i<=sqrt(n);i++)for(int j=0;j<=n;j++)if(j<i*i)dp[i][j]=dp[i-1][j];else   dp[i][j]=min(dp[i-1][j],dp[i][j-i*i]+1);return dp[sqrt(n)][n];}
};

4.滚动数组

和01背包优化一样,把第一维直接删掉就行

class Solution {
public:int numSquares(int n) {vector<unsigned> dp(n+1,INT_MAX/2);dp[0]=0;for(int i=1;i<=sqrt(n);i++)for(int j=i*i;j<=n;j++)dp[j]=min(dp[j],dp[j-i*i]+1);return dp[n];}
};

139.单词拆分(类比爬楼梯)

139. 单词拆分 - 力扣(LeetCode)

思路分析:

这道题和爬楼梯、组合总和IV基本一模一样,求的都是排列数量,只是多加了一个条件

Day40 | 动态规划 :完全背包应用 组合总和IV(类比爬楼梯)-CSDN博客

我们这么想,把wordDict里面的单词看做我们的物品,而把s这个字符串看做背包

类比爬楼梯

在70.爬楼梯中,我们每次从 nums 中选一个数,作为往上爬的台阶数,问爬 target 个台阶有多少种方案。70 那题可以看作 nums=[1,2],因为每次只能爬 1 个或 2 个台阶。

dp[i]的含义就是爬上第i个台阶的方案数量

1.在那道题中

我们的代码是

dp[i]=dp[i-1]+dp[i-2]

2.如果说我们一次可以爬k个台阶,当然k要比target(要爬的总楼梯数量)小

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+....+dp[i-k]
//等价于
for(int j=1;j<=k;j++)dp[i]+=dp[i-j];

3.如果说我们一次可以爬的台阶数量是nums数组里面的,那么j就是nums[j],上面的1-k就相当于这里的nums数组的遍历

dp[i]=dp[i-nums[1]]+dp[i-nums[2]]+dp[i-nums[3]]+....+dp[i-nums[nums.size()-1]]
//等价于
for(int j=0;j<nums.size();j++)dp[i]+=dp[i-nums[j]];

相当于,在第一种情况中

nums数组为{1,2}

在第二种情况中

nums数组为{1,2,3,…,k}

而本题中呢

我们要爬到s.size()这个台阶上,每次可以爬的台阶数量呢就是wordDict[i].size()这么多个台阶

从这里开始就和爬楼梯不同了,因为字符串s这个背包是一个有形状的背包

类似于这样

image-20241109173408456

这个背包长这个倒霉样子,如果不先放平行四边形,那这个背包永远也不会装满,即使你的三角形大小为3,平行四边形可能为9

这个意思就是说,我们这次往背包里面放物品不仅仅取决于背包容量,还要看它的形状,形状那就体现在咱们要放的字符串和背包的这一截一不一样

用爬楼梯的话说就是,能爬到s.size()级台阶的方法不能只是数量大小上面达到了,你走过的路径,你选择的字符串拼起来要能组成我的s字符串才是合法的方案,才能返回true

体现在代码中就是:

image-20241109174343757

爬楼梯这部分代码对应到本题,代码就会变成

for(int j=0;j<wordDict.size();j++)if(wordDict[j].size()<=i){string str;str=s.substr(i-wordDict[j].size(),wordDict[j].size());dp[i]=(str==wordDict[j]&&dp[i-wordDict[j].size()])||dp[i];}

dp[i]的含义是我们能不能用wordDict里面的字符串拼成s.begin()到s.begin()+i这个字符串,可以的话就是true,不行就是false,i是遍历背包容量

可以看到,在第一个if判断我们目前的背包可以装下这个字符串的时候,并不会立马放进去

(放进去就是(dp[i-wordDict[j].size()],不放就是dp[i])

而是把我们要放的字符串wordDict[i]和背包的某一截进行比较,如果一模一样的话,才会放进去

如果大家有点蒙圈的话,就再次对比一下爬楼梯,爬楼梯是看我这次爬nums[j]个台阶能不能爬到第i个台阶,这里我选这么些字符串(wordDict[j])能不能拼成s.begin()到s.begin()+i这个字符串

我可能是从第一个台阶爬两个到第三个台阶

我可能是从第二个台阶爬一个到第三个台阶

我可能是从已经拼好的部分再加上wordDict[1]就能拼成

我可能是从已经拼好的部分再加上wordDict[2]就能拼成

所以要把物品都给遍历一遍

难理解的点:||dp[i]的作用

这个是用来保留dp[i]的结果的

假如我运气好第一次循环就拼好了,dp[i]就是true,后面不管结果如果我就是true

但如果没有这个,我后面如果都没拼好过,那dp[i]就是false,就代表没有合法的方案,那这明显是错的

1.回溯法

1.参数和返回值

c是背包容量,我们要拼的字符串就是s.begin()到s.begin()+c

bool dfs(int c,string &s,vector<string>& wordDict)

2.终止条件

c==0,我们找到了合法方案,返回true

if(c==0)return true;

3.本层逻辑

这里就如上面所说,我就不过多解释了

		bool res=false;for(int i=0;i<wordDict.size();i++)if(c>=wordDict[i].size()){string str=s.substr(c-wordDict[i].size(),wordDict[i].size());res=(str==wordDict[i]&&dfs(c-wordDict[i].size(),s,wordDict))||res;}return res;

完整代码:

当然是超时的

class Solution {
public:bool dfs(int c,string &s,vector<string>& wordDict){if(c==0)return true;bool res=false;for(int i=0;i<wordDict.size();i++)if(c>=wordDict[i].size()){string str=s.substr(c-wordDict[i].size(),wordDict[i].size());res=(str==wordDict[i]&&dfs(c-wordDict[i].size(),s,wordDict))||res;}return res;}bool wordBreak(string s, vector<string>& wordDict) {return dfs(s.size(),s,wordDict);}
};
//lambda
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {function<bool(int)> dfs=[&](int c)->bool{if(c==0)return true;bool res=false;for(int i=0;i<wordDict.size();i++)if(c>=wordDict[i].size()){string str=s.substr(c-wordDict[i].size(),wordDict[i].size());res=(str==wordDict[i]&&dfs(c-wordDict[i].size()))||res;}return res;};return dfs(s.size());}
};

2.记忆化搜索

就是还是全都初始化为-1,每次返回前给dp赋值,碰到不是-1的那就是算过的,那就直接返回计算过的结果,不需要再次递归了

class Solution {
public:bool dfs(int c,string &s,vector<string>& wordDict,vector<int>& dp){if(c==0)return true;if(dp[c]!=-1)return dp[c];bool res=false;for(int i=0;i<wordDict.size();i++)if(c>=wordDict[i].size()){string str=s.substr(c-wordDict[i].size(),wordDict[i].size());res=(str==wordDict[i]&&dfs(c-wordDict[i].size(),s,wordDict,dp))||res;}return dp[c]=res;}bool wordBreak(string s, vector<string>& wordDict) {vector<int> dp(s.size()+1,-1);return dfs(s.size(),s,wordDict,dp);}
};
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<int> dp(s.size()+1,-1);function<bool(int)> dfs=[&](int c)->bool{if(c==0)return true;if(dp[c]!=-1)return dp[c];bool res=false;for(int i=0;i<wordDict.size();i++)if(c>=wordDict[i].size()){string str=s.substr(c-wordDict[i].size(),wordDict[i].size());res=(str==wordDict[i]&&dfs(c-wordDict[i].size()))||res;}return dp[c]=res;};return dfs(s.size());}
};

3. 1:1翻译为动态规划

回溯终止条件为c==0的时候返回true,那动态规划dp数组初始化就是dp[0]=true

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size()+1,false);dp[0]=true;for(int i=1;i<=s.size();i++)for(int j=0;j<wordDict.size();j++)if(wordDict[j].size()<=i){string str;str=s.substr(i-wordDict[j].size(),wordDict[j].size());dp[i]=(dp[i-wordDict[j].size()]&&str==wordDict[j])||dp[i];}return dp[s.size()];}
};

和完全背包一样,是求排列的先遍历容量后遍历物品的写法

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《 C++ 修炼全景指南:十九 》想懂数据库?深入 B 树的世界,揭示高效存储背后的逻辑

摘要 本文深入探讨了 B 树的原理、操作、性能优化及其实际应用。B 树作为一种平衡多路树结构&#xff0c;因其高效的查找、插入和删除操作广泛应用于数据库与文件系统中。文章首先介绍了 B 树的定义与性质&#xff0c;并详细阐述了节点分裂、合并等核心操作的实现方法。接着&a…

选择小练习

条件语句 if 条件语句&#xff0c;也叫作选择语句、判断语句。根绝特定条件判断是否成立&#xff0c;执行不同的语句段。简单来说&#xff0c;满足条件执行&#xff0c;不满足不执行。 条件语句是使用关键字 if 做判断&#xff0c;根据不同情况结合不同的关键字else 或者 eli…

单片机串口接收状态机STM32

单片机串口接收状态机stm32 前言 项目的芯片stm32转国产&#xff0c;国产芯片的串口DMA接收功能测试不通过&#xff0c;所以要由原本很容易配置的串口空闲中断触发DMA接收数据的方式转为串口逐字节接收的状态机接收数据 两种方式各有优劣&#xff0c;不过我的芯片已经主频跑…

BAAI 的 Aquila-VL-2B-llava-qwen: 促进视觉语言理解

简介 在人工智能领域&#xff0c;北京人工智能学会&#xff08;BAAI&#xff09;做出了重要贡献&#xff1a; 在人工智能领域&#xff0c;北京人工智能研究所&#xff08;BAAI&#xff09;开发的 Aquila-VL-2B-llava-qwen 模型做出了重大贡献。这一创新模型建立在 LLava-one-v…

测试实项中的偶必现难测bug--短信触发H5拒绝行为

问题描述: 企业邀请其他人加入团队,发送邀请短信给对方,对方通过短信链接跳转到H5页面,输入手机后,点击发送验证码,前提是短信通知验证弹窗需要打开,收到短信验证码后,点击一键代入,会触发拒绝加入行为。 需求: 由于我们的邀请链接是一次性的,一旦有用户确认加入或…

MCU的OTA升级(未完-持续更新)

1.术语 ISP : In-System Programming 在系统编程&#xff0c;是一种通过MCU&#xff08;微控制器单元&#xff09;上的内置引导程序&#xff08;BootLoader&#xff09;来实现对芯片内部存储器&#xff08;如Flash&#xff09;进行编程的技术。 华大目前对应的ISP IAP&…

即将盛大启幕“2025南京软件产业博览会·南京软博会”

在今年的南京软博会上&#xff0c;科技创新的浪潮再次席卷了整个会展现场&#xff0c;来自全球的软件产业精英们汇聚一堂&#xff0c;共同见证了软件产业的最新成果与未来趋势。随着云计算、大数据、人工智能等新兴技术的蓬勃发展&#xff0c;软件产业正站在一个前所未有的历史…

npm : 无法加载文件 C:\Program Files\nodejs\npm.ps1,因为在此系统上禁止运行脚本。

npm : 无法加载文件 C:\Program Files\nodejs\npm.ps1&#xff0c;因为在此系统上禁止运行脚本。有关详细信息&#xff0c;请参阅 https:/go.microsoft.com/fwlink/?LinkID135170 中的 about_Exe cution_Policies。 所在位置 行:1 字符: 1 npm install ~~~ CategoryInf…

网管平台(进阶篇):如何正确的管理网络设备?

网络设备作为构建计算机网络的重要基石&#xff0c;扮演着数据传输、连接和管理的关键角色。从交换机、路由器到防火墙、网关&#xff0c;各类网络设备共同协作&#xff0c;形成了高效、稳定的网络系统。本文将详细介绍网络设备的种类&#xff0c;并探讨如何正确管理这些设备&a…

【Linux】【Vim】多文件编辑与分屏

多文件编辑 编辑另一个文件文件列表分屏vimdiff文件跳转 编辑另一个文件 除了为每一个要编辑的文件运行一次 Vim 之外&#xff0c;还可以在当前 Vim 中开始编辑另一个文件。 :edit foo.txtVim 会关闭当前正在编辑的文件打开指定的新文件进行编辑。如果当前文件还有未存盘的内容…

从零开始训练一个大语言模型需要多少天?

一&#xff0c;前言 在AI领域&#xff0c;训练一个大型语言模型&#xff08;LLM&#xff09;是一个耗时且复杂的过程。几乎每个做大型语言模型&#xff08;LLM&#xff09;训练的人都会被问到&#xff1a;“从零开始&#xff0c;训练大语言模型需要多久和花多少钱&#xff1f;”…

潮玩宇宙方块兽系统开发:可定制UI与多种游戏内嵌助力个性化体验

潮玩宇宙方块兽系统开发正在推动潮玩与游戏的融合&#xff0c;通过个性化的UI设计和多游戏内嵌模式&#xff0c;为用户带来了独一无二的体验。本文将从可定制UI、多游戏内嵌功能以及系统实现等方面入手&#xff0c;探讨如何构建一个极具吸引力的潮玩宇宙方块兽系统。 一、可定制…

git提交顺序为什么是:add,conmmit,pull,push

git提交顺序为什么是&#xff1a;add,conmmit,pull,push 01. add,conmmit,pull,push的顺序问题02. 扩展&#xff1a;git上传常用的六个命令包括&#xff1a;add、commit、push、clone、pull、fetch。 add&#xff1a;将文件添加到暂存区 commit&#xff1a;将暂存区中的文件提交…

服务器数据恢复—EVA存储故障导致上层应用不可用的数据恢复案例

服务器存储数据恢复环境&#xff1a; 一台EVA某型号控制器EVA扩展柜FC磁盘。 服务器存储故障&检测&#xff1a; 磁盘故障导致该EVA存储中LUN不可用&#xff0c;导致上层应用无法正常使用。 服务器存储数据恢复过程&#xff1a; 1、将所有磁盘做好标记后从扩展柜中取出。硬…

解决编译 fast-lio-lc 算法时遇到的error方法

1.创建工作空间和下载 fast-lio-lc功能包 mkdir -p fast_lio_lc_ws/src cd fast_lio_lc_ws/src/ catkin_init_workspace git clone https://github.com/yanliang-wang/FAST_LIO_LC.git2.进入工作空间,编译 编译 fast-lio-lc遇到的error: 🕐error: fatal error: opencv/cv…

软件著作权申请教程(超详细)(2024新版)软著申请

目录 一、注册账号与实名登记 二、材料准备 三、申请步骤 1.办理身份 2.软件申请信息 3.软件开发信息 4.软件功能与特点 5.填报完成 一、注册账号与实名登记 首先我们需要在官网里面注册一个账号&#xff0c;并且完成实名认证&#xff0c;一般是注册【个人】的身份。中…

鸿蒙ArkTS中的布局容器组件(Scroll、List、Tabs)

1、Scroll组件 Scroll组件是一个可滚动的容器组件&#xff0c;用于在子组件的布局尺寸超过父组件尺寸时提供滚动功能。它允许在其内部容纳超过自身显示区域的内容&#xff0c;并通过滚动机制来查看全部内容。这对于显示大量信息&#xff08;如长列表、长篇文本或大型图像等&…

webWorker基本用法

我们都知道js是一个单线程的语言&#xff0c;当线程堵塞时&#xff0c;可能会导致页面无法正常交互&#xff0c;如一些复杂的可视化处理。即使是异步处理&#xff0c;也只是将其暂存到任务队列中去&#xff0c;等主线程执行完后依然会从任务队列中取过去。 为此&#xff0c;js提…

《手写Spring渐进式源码实践》实践笔记(第十八章 JDBC功能整合)

文章目录 第十八章 JDBC功能整合背景技术背景JDBC JdbcTemplate关键特性 用法示例业务背景 目标设计实现代码结构类图实现步骤 测试事先准备属性配置文件测试用例测试结果&#xff1a; 总结 第十八章 JDBC功能整合 背景 技术背景 JDBC JDBC&#xff08;Java Database Conne…

【Python】轻松实现机器翻译:Transformers库使用教程

轻松实现机器翻译&#xff1a;Transformers库使用教程 近年来&#xff0c;机器翻译技术飞速发展&#xff0c;从传统的基于规则的翻译到统计机器翻译&#xff0c;再到如今流行的神经网络翻译模型&#xff0c;尤其是基于Transformer架构的模型&#xff0c;翻译效果已经有了质的飞…