代码随想录算法训练营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 的博客 💞💞💞 “仅仅活着是不够的,还需要有阳光,自由和花的芬芳。” 前言: 在日常使用的网站和软件中,列表属于最常见的一种东西了,其实现形式有顺序表࿰…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...