当前位置: 首页 > news >正文

代码随想录算法训练营第四十六天 | 139.单词拆分,多重背包,背包问题总结

目录

139.单词拆分

多重背包

背包问题总结

01背包

完全背包

多重背包


139.单词拆分

题目链接:139. 单词拆分

不要求字典中的单词全部使用,但是要求拆分的单词拆分成的每一个子串都是字典中的单词。

(1)dp[ i ] 表示前 i 个字符组成的字符串可以被字典中的单词拆分;

(2)dp[ i ] = dp[ j ] && check(str, i - j + 1);

(3)均初始化为false;

(4)强调子串顺序,外层遍历背包,内层遍历物品;

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);if(dp[j] && (wordSet.find(word) != wordSet.end()))dp[i] = true;}}return dp[s.size()];}
};

dp数组的更新并没有像我五部曲那样写,因为并不是每次dp[ i ] 都需要更新。

多重背包

多重背包中,将 物品的数量 转化为 数量个相同的物品,转化成 01背包问题;

C++ 实现中时在循环中遍历数量。

背包问题总结

01背包

物品数量为 1,循环顺序:外层遍历物品、内层从大到小遍历背包容量。

完全背包

物品数量无限;循环顺序:(1)组合问题:外层遍历物品、内层从小到大遍历背包容量;(2)排列问题:外层遍历背包容量,内层遍历物品。

多重背包

转化为 01背包。

相关文章:

代码随想录算法训练营第四十六天 | 139.单词拆分,多重背包,背包问题总结

目录 139.单词拆分 多重背包 背包问题总结 01背包 完全背包 多重背包 139.单词拆分 题目链接&#xff1a;139. 单词拆分 不要求字典中的单词全部使用&#xff0c;但是要求拆分的单词拆分成的每一个子串都是字典中的单词。 &#xff08;1&#xff09;dp[ i ] 表示前 i 个字符组成…...

opencv-Canny 边缘检测

Canny边缘检测是一种经典的图像边缘检测算法&#xff0c;它在图像中找到强度梯度的变化&#xff0c;从而识别出图像中的边缘。Canny边缘检测的优点包括高灵敏度和低误检率。 在OpenCV中&#xff0c;cv2.Canny() 函数用于执行Canny边缘检测。 基本语法如下&#xff1a; edges…...

案例023:基于微信小程序的童装商城的设计与实现

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…...

Ansible的循环:loop,with_<lookup>和until

环境 管理节点&#xff1a;Ubuntu 22.04控制节点&#xff1a;CentOS 8Ansible&#xff1a;2.15.6 循环的方法 loopwith_<lookup>until 用这几种方式都可以实现循环。其中&#xff0c; loop 是推荐的用法&#xff0c;在很多时候能够替换 with_<lookup> 。 loop…...

点云 surface 方法总结

点云的表面方法是指通过点云数据来估计和重建物体或场景的表面几何形状。下面总结了几种常见的点云表面方法&#xff1a; 三角化&#xff1a;三角化是最常用的点云表面重建方法之一。它将点云中的点连接成三角形网格&#xff0c;从而重建出物体或场景的表面。常见的三角化算法…...

深入探索Linux文件系统:属性、路径与隐藏之谜

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Linux系统理论 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言&#x1f324;️文件的组成☁️文件属性☁️文件内容☁️注意事项 &#x1f324;️路…...

梯度详解与优化实战

什么是梯度 对所有自变量求偏微分构成的向量&#xff0c;它是一个向量&#xff08;有大小和函数值增长方向&#xff09; 导数是一个标量 找最小值点坐标的案例 import torchimport numpy as np import matplotlib.pyplot as plt def himmelblau(x):return (x[0]**2x[1]-11)…...

OSG编程指南<十二>:OSG二三维文字创建及文字特效

1、字体基础知识 适当的文字信息对于显示场景信息是非常重要的。在 OSG 中&#xff0c;osgText提供了向场景中添加文字的强大功能&#xff0c;由于有第三方插件 FreeType 的支持&#xff0c;它完全支持TrueType 字体。很多人可能对 FreeType 和 TrueType 还不太了解&#xff0c…...

visionOS空间计算实战开发教程Day 6 拖拽和点击

在之前的学习中我们在空间中添加了3D模型&#xff0c;但在初始摆放后就无法再对其进行移动或做出修改。本节我们在​​Day 5​​显示和隐藏的基础上让我们模型可以实现拖拽效果&#xff0c;同时对纯色的立方体实现点击随机换色的功能。 首先是入口文件&#xff0c;无需做出改变…...

C# APS.NET CORE 6.0 WEB API IIS部署

1.创建 APS.NET CORE6.0 WEB API项目 默认选项即可 源代码&#xff1a; 项目文件展开&#xff1a; launchSettings.json {"$schema": "https://json.schemastore.org/launchsettings.json","iisSettings": {"windowsAuthentication"…...

C/C++ 常用加密与解密算法

计算机安全和数据隐私是现代应用程序设计中至关重要的方面。为了确保数据的机密性和完整性&#xff0c;常常需要使用加密和解密算法。C是一种广泛使用的编程语言&#xff0c;提供了许多加密和解密算法的实现。本文将介绍一些在C中常用的加密与解密算法&#xff0c;这其中包括Xo…...

从Qt源码的角度分析Qt对象树与内存管理模式

作者:令狐掌门 技术交流QQ群:675120140 csdn博客:https://mingshiqiang.blog.csdn.net/ 文章目录 一、Qt对象树(Object Tree)和父子关系二、源码角度:QObject的内存管理构造函数析构函数addChild() 和 removeChild()三、C++模拟实现Qt的对象树内存管理模式Qt框架提供了一…...

MySQL与Redis如何保证数据的一致性

文章目录 MySQL与Redis如何保证数据的一致性&#xff1f;不好的方案1. 先写 MySQL&#xff0c;再写 Redis2. 先写 Redis&#xff0c;再写 MySQL3. 先删除 Redis&#xff0c;再写 MySQL 好的方案4. 先删除 Redis&#xff0c;再写 MySQL&#xff0c;再删除 Redis5. 先写 MySQL&am…...

micropython - espnow

espnow这个东西可以很简单的进行多设备近距离互联&#xff0c;连握手都不用注册一下就能发信息 目前8266那个8角的刷20231105的1M的固件可以运行 8266目前没有信号强度功能所以我自己写的类强度返回为0 我写的类实例化后最后注册谁发消息就是给谁而接收端则是什么都接&#xff…...

京东数据采集(京东数据运营):怎样快速获取京东市场大数据?

相信京东平台的很多品牌方们都有做数据分析的需求&#xff0c;但面对多而杂的市场数据&#xff0c;很多运营者都没有思路。单依靠肉眼来看&#xff0c;很多商品的类目、销售成绩、价格分布等运营者也未必清楚。 其实对于京东平台上市场数据的获取&#xff0c;品牌可以直接借助一…...

​重生奇迹mu迷宫攻略​

重生奇迹mu迷宫是一种比较有挑战性的游戏玩法&#xff0c;需要一定的技巧和策略才能完成。以下是一些基本的攻略和技巧&#xff1a; 了解每个迷宫的特点&#xff1a;不同的迷宫有不同的规则和特点&#xff0c;需要根据迷宫的特点来制定合理的策略。在进入迷宫前可以先了解一下…...

[网络] 4. HTTP/1.1 相比 HTTP/1.0 提高了什么性能?

HTTP/1.1 相比 HTTP/1.0 性能上的改进 ● 使用长连接的方式改善了 HTTP/1.0 短连接造成的性能开销。 ● 支持管道&#xff08;pipeline&#xff09;网络传输&#xff0c;只要第一个请求发出去了&#xff0c;不必等其回来&#xff0c;就可以发第二个请求出去&#xff0c;可以减…...

3.1.2 Linux时间子系统 hrtimer示例使用

文章目录 结构体定义接口初始化启动修改取消示例示例1示例2示例3结构体定义 struct hrtimer {struct timerqueue_node node;ktime_t _softexpires;enum hrtimer_restart...

04 _ 系统设计目标(二):系统怎样做到高可用?

这里将探讨高并发系统设计的第二个目标——高可用性。 高可用性&#xff08;High Availability&#xff0c;HA&#xff09;是你在系统设计时经常会听到的一个名词&#xff0c;它指的是系统具备较高的无故障运行的能力。 我们在很多开源组件的文档中看到的HA方案就是提升组件可…...

Android相机性能提高50%

文章目录 应用举例&#xff08;可以不看这一part&#xff0c;直接跳过看具体怎么做&#xff09;&#xff1a;Snapchat 通过 Camera2 Extensions API 将新相机功能的集成速度提高了 50%**Camera2 扩展 API 可以访问高级功能更多设备上的更多机会 正文&#xff1a;开始使用扩展架…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...