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

Day40- 动态规划part08

一、单词拆分

题目一:139. 单词拆分

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

定义一个布尔型的动态规划数组dp

dp[i]表示字符串s的前i个字符能否被字典wordDict中的一个或多个单词拼接出来

dp[0]为真,因为空字符串总是可以被拼接出来的

对于字符串s中的每一个位置i(从1到字符串长度),遍历i之前的所有位置j(从0到i-1),检查从ji的子字符串是否存在于字典wordDict

/** @lc app=leetcode.cn id=139 lang=cpp** [139] 单词拆分*/// @lc code=start
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end());vector<bool> dp(s.length() + 1, false);dp[0] = true; // 空字符串总是可以被拼接for (int i = 1; i <= s.length(); ++i) {for (int j = 0; j < i; ++j) {if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {dp[i] = true;break; // 找到一种拼接方式即可}}}return dp[s.length()];}
};
// @lc code=end

二、多重背包

56. 携带矿石资源(第八期模拟笔试)

时间限制:5.000S  空间限制:256MB

题目描述

你是一名宇航员,即将前往一个遥远的行星。在这个行星上,有许多不同类型的矿石资源,每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球,但你的宇航舱有一定的容量限制。 

给定一个宇航舱,最大容量为 C。现在有 N 种不同类型的矿石,每种矿石有一个重量 w[i],一个价值 v[i],以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下,最大化你所能获取的总价值。

输入描述

输入共包括四行,第一行包含两个整数 C 和 N,分别表示宇航舱的容量和矿石的种类数量。 

接下来的三行,每行包含 N 个正整数。具体如下: 

第二行包含 N 个整数,表示 N 种矿石的重量。 

第三行包含 N 个整数,表示 N 种矿石的价格。 

第四行包含 N 个整数,表示 N 种矿石的可用数量上限。

输出描述

输出一个整数,代表获取的最大价值。

动态规划数组dp[j]表示容量为j的背包所能装下的最大价值。对于每种矿石i,遍历背包容量j从大到小,更新dp[j]

具体实现步骤如下:

  1. 对于每种矿石i,将其按数量k[i]进行二进制拆分,比如如果k[i] = 4,可以拆分为1,2,1(共计4个),这样就将问题转化为了多个0-1背包问题。
  2. 对于每个拆分后的矿石,更新dp[j]
#include <iostream>
#include <vector>
using namespace std;int main() {int C, N;cin >> C >> N;vector<int> w(N), v(N), k(N);for (int i = 0; i < N; ++i) cin >> w[i];for (int i = 0; i < N; ++i) cin >> v[i];for (int i = 0; i < N; ++i) cin >> k[i];vector<int> dp(C + 1, 0);for (int i = 0; i < N; ++i) {int num = k[i];for (int k = 1; num > 0; k *= 2) { int mul = min(k, num);int weight = w[i] * mul;int value = v[i] * mul;for (int j = C; j >= weight; --j) {dp[j] = max(dp[j], dp[j - weight] + value);}num -= mul;}}cout << dp[C] << endl;return 0;
}

相关文章:

Day40- 动态规划part08

一、单词拆分 题目一&#xff1a;139. 单词拆分 139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以…...

论文笔记:相似感知的多模态假新闻检测

整理了RecSys2020 Progressive Layered Extraction : A Novel Multi-Task Learning Model for Personalized Recommendations&#xff09;论文的阅读笔记 背景模型实验 论文地址&#xff1a;SAFE 背景 在此之前&#xff0c;对利用新闻文章中文本信息和视觉信息之间的关系(相似…...

5G技术对物联网的影响

随着数字化转型的加速&#xff0c;5G技术作为通信领域的一次重大革新&#xff0c;正在对物联网&#xff08;IoT&#xff09;产生深远的影响。对于刚入行的朋友们来说&#xff0c;理解5G技术及其对物联网应用的意义&#xff0c;是把握行业发展趋势的关键。 让我们简单了解什么是…...

Nacos1.X源码解读(待完善)

目录 下载源码 注册服务 客户端注册流程 注册接口API 服务端处理注册请求 设计亮点 服务端流程图 下载源码 1. 克隆git地址到本地 # 下载nacos源码 git clone https://github.com/alibaba/nacos.git 2. 切换分支到1.4.7, maven编译(3.5.1) 3. 找到启动类com.alibaba.na…...

算法之双指针系列1

目录 一&#xff1a;双指针的介绍 1&#xff1a;快慢指针 2&#xff1a;对撞指针 二&#xff1a;对撞指针例题讲述 一&#xff1a;双指针的介绍 在做题中常用两种指针&#xff0c;分别为对撞指针与快慢指针。 1&#xff1a;快慢指针 简称为龟兔赛跑算法&#xff0c;它的基…...

苍穹外卖面试题

8. 如何理解分组校验 很多情况下&#xff0c;我们会将校验规则写到实体类中的属性上&#xff0c;而这个实体类有可能作为不同功能方法的参数使用&#xff0c;而不同的功能对象参数对象中属性的要求是不一样的。比如我们在新增和修改一个用户对象时&#xff0c;都会接收User对象…...

【Qt 学习之路】在 Qt 使用 ZeroMQ

文章目录 1、概述2、ZeroMQ介绍2.1、ZeroMQ 是什么2.2、ZeroMQ 主线程与I/O线程2.3、ZeroMQ 4种模型2.4、ZeroMQ 相关地址 3、Qt 使用 ZeroMQ3.1、下载 ZeroMQ3.2、添加 ZeroMQ 库3.3、使用 ZeroMQ3.4、相关 ZeroMQ 案例 1、概述 今天是大年初一&#xff0c;先给大家拜个年&am…...

CI/CD到底是啥?持续集成/持续部署概念解释

前言 大家好&#xff0c;我是chowley&#xff0c;日常工作中&#xff0c;我每天都在接触CI/CD&#xff0c;今天就给出我心中的答案。 在现代软件开发中&#xff0c;持续集成&#xff08;Continuous Integration&#xff0c;CI&#xff09;和持续部署&#xff08;Continuous D…...

golang常用库之-disintegration/imaging图片操作(生成缩略图)

文章目录 golang常用库之什么是imaging库导入和使用生成缩略图 golang常用库之 什么是imaging库 官网&#xff1a;https://github.com/disintegration/imaging imaging 是一个 Go 语言的图像处理库&#xff0c;它提供了一组功能丰富的函数和方法&#xff0c;用于进行各种图像…...

CSS 控制 video 标签的控制栏组件的显隐

隐藏下载功能 <video src"" controlsList"nodownload" />controlslist 取值如下(设定多个值则使用空格进行间隔) 如&#xff1a;controlslist"nodownload nofullscreen noremoteplayback"nodownload&#xff1a;取消更多控件弹窗的下载功…...

数据可视化之维恩图 Venn diagram

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 维恩图&#xff08;Venn diagram&#xff09;&#xff0c;也叫文氏图或韦恩图&#xff0c;是一种关系型图表&#xff0c;用于显示元素集合之间的重叠区…...

2024刘谦春晚第二个扑克牌魔术

前言 就是刚才看春晚感觉这个很神奇&#xff0c;虽然第一个咱模仿不过来&#xff0c;第二个全国人民这么多人&#xff0c;包括全场观众都有成功&#xff0c;这肯定是不需要什么技术&#xff0c;那我觉得这个肯定就是数学了&#xff0c;于是我就胡乱分析一通。 正文 首先准备…...

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…...

Rust变量与常量介绍

Rust是一门注重安全性和性能的系统编程语言&#xff0c;其中变量和常量的概念有着独特的设计和特性。在本文中&#xff0c;我们将深入了解Rust中的变量和常量&#xff0c;并解释它们之间的区别&#xff0c;同时通过多个例子进行说明。 Rust常量 在Rust中&#xff0c;常量是不…...

Flask基础学习2

连接mysql数据库测试(专业版) [注意1&#xff1a;要导入text库&#xff0c;否则可能出现找不到select 1错误] [注意2&#xff1a;若出现下列问题&#xff0c;可按照模板代码的顺序db SQLAlchemy(app) 的位置] RuntimeError: Either SQLALCHEMY_DATABASE_URI or SQLALCHEMY_B…...

文章页的上下篇功能是否有必要?boke112百科取消上下篇功能

也不知道是从什么时候开始&#xff0c;我们很多站长的博客网站文章页都会在文末添加上“上一篇”和“下一篇”功能&#xff0c;目的是进行站内SEO优化和方便用户阅读上下篇文章。 boke112百科不管是以前使用的Three主题还是现在使用的YIA主题&#xff0c;刚开始的文章页都是有…...

Lua序列化

我们经常需要序列化一些数据&#xff0c;为了将数据转换为字节流或者字符流&#xff0c;这样我们就可以保存到文件或者通过网络发送出去。我们可以在 Lua 代码中描述序列化的数据&#xff0c;在这种方式下&#xff0c;我们运行读取程序即可从代码中构造出保存的值。 number/st…...

Acwing---839. 模拟堆

模拟堆 1.题目2.基本思想3.代码实现 1.题目 维护一个集合&#xff0c;初始时集合为空&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个数 x&#xff1b;PM&#xff0c;输出当前集合中的最小值&#xff1b;DM&#xff0c;删除当前集合中的最小值&#xff08…...

STM32 STD/HAL库驱动W25Q64模块读写字库数据+OLED0.96显示例程

STM32 STD/HAL库驱动W25Q64 模块读写字库数据OLED0.96显示例程 &#x1f3ac;原创作者对W25Q64保存汉字字库演示&#xff1a; W25Q64保存汉字字库 &#x1f39e;测试字体显示效果&#xff1a; &#x1f4d1;功能实现说明 利用W25Q64保存汉字字库&#xff0c;OLED显示汉字的时…...

Android 移动应用开发 创建第一个Android项目

文章目录 一、创建第一个Android项目1.1 准备好Android Studio1.2 运行程序1.3 程序结构是什么app下的结构res - 子目录&#xff08;所有图片、布局、字AndroidManifest.xml 有四大组件&#xff0c;程序添加权限声明 Project下的结构 二、开发android时&#xff0c;部分库下载异…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...