代码随想录算法训练营day46 | 动态规划之背包问题 139.单词拆分
day46
- 139.单词拆分
- 1.确定dp数组以及下标的含义
- 2.确定递推公式
- 3.dp数组如何初始化
- 4.确定遍历顺序
- 5.举例推导dp[i]
139.单词拆分
题目链接
解题思路:单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词,说明就是一个完全背包!
动规五部曲分析如下:
1.确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。
2.确定递推公式
如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3.dp数组如何初始化
从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。
那么dp[0]有没有意义呢?
dp[0]表示如果字符串为空的话,说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
4.确定遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包。
还要讨论两层for循环的前后顺序。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
做一个总结:
而本题其实我们求的是排列数,为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。
所以说,本题一定是 先遍历 背包,再遍历物品。
5.举例推导dp[i]
以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例,dp状态如图:

dp[s.size()]就是最终结果。
动规五部曲分析完毕,C++代码如下:
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) { // 遍历背包for (int j = 0; j < i; j++) { // 遍历物品string word = s.substr(j, i - j); //substr(起始位置,截取的个数)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};相关文章:
代码随想录算法训练营day46 | 动态规划之背包问题 139.单词拆分
day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分 题目链接 解题思路:单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。…...
DPDK中的无锁共享数据结构
目录背景解决方法共享内存无锁操作新/老共享数据结构rte_ringrefcnt延迟释放方法1:读的线程来释放方法2:释放线程等到读线程轮询一轮参考背景 dpvs多线程,如何做到节约内存、高性能之间的均衡。 解决方法 共享内存 多线程共享内存&#x…...
【使用两个栈实现队列】
文章目录一、栈和队列的基本特点二、基本接口函数的实现1.栈的接口2.创建队列骨架3.入队操作4.取出队列元素5.返回队首元素6.判断队列是否为空7.销毁队列总结一、栈和队列的基本特点 栈的特点是后进先出,而队列的特点是先进先出。 使用两个栈实现队列,必…...
web,h5海康视频接入监控视频流记录一
项目需求,web端实现海康监控视频对接接入,需实现实时预览,云台功能,回放功能。 web端要播放视频,有三种方式,一种是装浏览器装插件,一种是装客户端exe,还有就是无插件了。浏览器装插…...
做毕业设计,前端部分你需要掌握的6个核心技能
其实前端新手如果想要自己实现一套毕业设计项目并非简单的事,因为之前很多人一直还停留在知识点的阶段,而且管理系统和C端网站都需要开发,但现在需要点连成线了。所以在启动项目开发之前呢,针对前端部分,我列举一些非常…...
Read book Netty in action(Chapter VIII)--EventLoop and thread model
前言 简单地说,线程模型指定了操作系统、编程语言、框架或者应用程序的上下文中的线程管理的关键方面。显而易见地,如何以及何时创建线程将对应用程序代码的执行产生显著的影响,因此开发人员需要理解与不同模型相关的权衡。无论是他们自己选…...
番外11:使用ADS对射频功率放大器进行非线性测试3(使用带宽5MHz的WCDMA信号进行ACLR测试)
番外11:使用ADS对射频功率放大器进行非线性测试3(使用带宽5MHz的WCDMA信号进行ACLR测试) 其他测试: 番外9:使用ADS对射频功率放大器进行非线性测试1(以IMD3测试为例) 番外10:使用AD…...
Linux libpqxx 库安装及使用
记录一下linux安装 libpqxx遇到的一些问题 1.准备安装包: 1.准备安装包,以libpqxx-4.0.1.tar.gz为例子 链接如下:https://launchpad.net/libpqxx/milestone/4.0.1 2.上传并安装 上传到安装目录并安装,我是放到/use/local下面 c…...
如何使用COM-Hunter检测持久化COM劫持漏洞
关于COM-Hunter COM- Hunter是一款针对持久化COM劫持漏洞的安全检测工具,该工具基于C#语言开发,可以帮助广大研究人员通过持久化COM劫持技术来检测目标应用程序的安全性。 关于COM劫持 微软在Windows 3.11中引入了(Component Object Model, COM)&…...
Cartesi 举办的2023 黑客马拉松
Cartesi 是具有 Linux 运行时的特定于应用程序的Rollups执行层。Cartesi 的特定应用程序 Optimistic Rollup 框架使区块链堆栈足够强大,开发人员可以构建计算密集型和以前不可能的去中心化实例。Cartesi 的 RISC-V 虚拟机支持 Linux 运行时环境,允许像你…...
架构篇--代码质量手册
目前团队缺少SA(研发经理)的角色,大家代码写的有点随意,老板让我写一份开发手册。嗯!!!当时我稍微纠结了一下,感觉这个似乎不是我的工作范畴,但是本着"我就是块砖&a…...
那些年用过的IDEA插件
今天和大家分享一下经常使用的IDEA的插件,希望有所帮助。一、IDEA插件CodeGlance2显示代码缩略图插件,方便查看代码。Lombok用于编译期间自动生成getter、setter、构造、toString等方法,简化代码。Mybatis Builder或MybatisXMapper接口和xml双…...
python+requests实现接口自动化测试
这两天一直在找直接用python做接口自动化的方法,在网上也搜了一些博客参考,今天自己动手试了一下。 一、整体结构 上图是项目的目录结构,下面主要介绍下每个目录的作用。 Common:公共方法:主要放置公共的操作的类,比如数据库sqlhe…...
rtthread 线程
创建动态线程最简单代码 #include <rtthread.h>//包含头文件static rt_thread_t thread1 RT_NULL; //创建线程控制块指针,指向空static void thread1_entry(void *parameter)//线程入口(干什么) {rt_kprintf("do something"…...
伯恩光学再成被执行人:多次因劳动纠纷被起诉,曾冲刺港交所上市
近日,贝多财经从天眼查APP了解到,伯恩光学(深圳)有限公司(下称“伯恩光学”)因《伯恩光学(深圳)有限公司与温*燕劳动合同纠纷的案件》一事,被广东省深圳市龙岗区人民法院…...
mysql基础操作2
通配符_:一个任意字符,like ‘张_’%:任意长度的字符串,like ‘co%’,‘%co’,‘%co%’【】:括号中所指定范围内的一个字符,like ‘9W0【1-2】’【^】:不在括号中所指定范…...
指针的进阶【下篇】
文章目录📀8.指向函数指针数组的指针📀9.回调函数📀8.指向函数指针数组的指针 🌰请看代码与注释👇 int Add(int x, int y) {return x y; } int Sub(int x, int y) {return x - y; } int main() {int (*pf)(int, int…...
不同序列模型的输入和输出总结
不同序列模型的输入和输出总结 文章目录不同序列模型的输入和输出总结RNNLSTMGRURNN RNN 是迭代输出: 输入第一个 -> 输出第二个, 输入第二个 -> 输出第三个, 输出倒数第二个 -> 输出最后一个。 LSTM LSTM 也是迭代输出ÿ…...
基于神经网络补偿的主动悬架自适应控制
目录 前言 1. 1/4悬架模型 2.仿真分析 2.1仿真模型 2.2仿真结果 2.1 形① 2.2 形② 3. 总结 前言 上两篇博客我们介绍了神经网络补偿控制律的仿真测试,从仿真结果我们可以得知神经网络具有逼近扰动,并将其补偿的作用。 上两篇文章链接…...
什么是链表,如何实现?(单链表篇)
欢迎来到 Claffic 的博客 💞💞💞 “仅仅活着是不够的,还需要有阳光,自由和花的芬芳。” 前言: 在日常使用的网站和软件中,列表属于最常见的一种东西了,其实现形式有顺序表࿰…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
