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

探针台简介
探针台,是我们半导体实验室电学性能测试的常用设备,也是各大实验室以及芯片设计、封装测试的熟客。设备具备各项优势,高性能低成本,用途广,操作方便,在不同测试环境下,测试结果稳定,…...

ABAP 辨析 标准表|排序表|哈希表
1、文档介绍 本文档将介绍内表的区别和用法,涉及标准表、排序表、哈希表 2、用法与区别 2.1、内表种类 内表顶层为任意表,任意表分为索引表和哈希表,索引表又可分为标准表和排序表,结构如图: 2.2、内表用法 2.2.1…...

MIGO 物料过账 创建物料凭证 BAPI_GOODSMVT_CREATE
文章目录1.前台操作2.需求分析2.1调用方式2.2分为两大概括:2.3业务逻辑细节图3.BAPI_GOODSMVT_CREATE4.RFC接口代码5.总结1.前台操作 SAP CO01(创建生产订单)/MIGO(发货投料)前台操作 这里面有migo的前台操作,首先了解前台操作后再去写RFC接口是比较容易理解的.!! 2.需求分析…...

项目经理处理团队冲突 5大注意事项
1、在时间、场景、体验矩阵中的5种处理方式 第一种方式:强迫命令,即职位高的一方在不考虑对方感受的情况下,强迫职位低的一方接受自己的意见。这种处理方式的适用场景为重要且紧急,这种方式团队成员的体验感低。 第二种方式&#…...

Linux(Centos)安装TDengine
目录1:简介2:前期准备3:安装4:启动5:开机自启动6:安装客户端驱动(如果别的服务器需要链接TD则需要此步操作)7:基础命令1:简介 官网: https://www.taosdata.com/简介&…...

大数据处理技术导论(6) | Datawhale组队学习46期
文章目录1. hive 概述2. hive 与传统关系型数据库的对比3. hive 数据类型4. hive 数据模型5. hive 实战5.1 创建表5.2 修改表5.3 清空表、删除表5.4 其他命令项目地址 https://github.com/datawhalechina/juicy-bigdata,感谢项目团队的付出。本次主要学习 hive 相关…...

Java——异常
目录 什么是异常 异常处理主要的5个关键字 异常的体系结构 异常语法 异常的分类 异常的处理流程 异常的处理 防御式编程 异常的抛出 throw的注意事项 异常的捕获 异常声明throws try-catch捕获处理 finally 自定义异常类 throw和throws区别 什么是异常 程序在运行时出现错…...

Netty之io.netty.util.concurrent.Promise与io.netty.util.concurrent.Future初解
目录 目标 Netty版本 Netty官方API 三者之间的关系 基本使用方法 java.util.concurrent.Future io.netty.util.concurrent.Future io.netty.util.concurrent.Promise 目标 了解io.netty.util.concurrent.Promise与io.netty.util.concurrent.Future的基本使用方法。了解…...

【正点原子FPGA连载】第二十一章AXI DMA环路测试 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南
1)实验平台:正点原子MPSoC开发板 2)平台购买地址:https://detail.tmall.com/item.htm?id692450874670 3)全套实验源码手册视频下载地址: http://www.openedv.com/thread-340252-1-1.html 第二十一章AXI D…...

手把手搭建springboot项目06-springboot整合RabbitMQ及其原理和应用场景
目录前言工作流程-灵魂画手名词解释交换机类型一、安装1.1 [RabbitMQ官网安装](https://www.rabbitmq.com/download.html)1.2 Docker安装并启动二、食用教程2.1.导入依赖2.2 添加配置2.3 代码实现2.3.1 直连(Direct)类型2.3.2 引入消息手动确认机制2.3.2…...