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

代码随想录打卡—day46—【DP】— 8.29 背包END

1 139. 单词拆分

139. 单词拆分

做了很久...估计2h 一开始我的思路卡死了 + 看题解之后的思路的详解见注释,

我的写法和carl 答案在一些微小的细节上略有不同,我的更好理解,但他的解法更简单。

我写的过程中,需要注意下标和字符串大小的关系要不要+1-1,而且dp[] 需要从1开始到n有意义,dp[0] 不管它。不可以只有0,...,n-1 这样会忽略s = "a" Dict = ["b"] 这样的样例,因为dp[0] 恒为1。

AC代码:

class Solution {
public://多重背包且排列/*一开始我的思路——物品:字典里面str背包:容量为?的背包  求装满时候的情况dp[wordDict.size()][s.size()]如果n = wordDict.size() m = s.size()  又感觉要考虑每个字符和Dict中每个字符串的关系 很麻烦        *//*看了题解,才知道我纠结的地方 每个字符和Dict中每个字符串的关系 很麻烦,但其实可以用substr函数考虑背包的s的子串和Dict中每个字符串来比较,这样就变得很简单了。而且之前思考时候不知道dp[]存的值要是int还是char什么东西其实就题目结果反推,dp[] = trur/flase*/bool dp[310];   //以i结尾的字符串是否可以利用字典中出现的单词拼接出来/*dp[j] = dp[j - wordDict[i].size()] && substr(s,j - wordDict[i].size(),wordDict[i].size()) == wordDict[i];dp[0] = 1;多重背包+排列背包j++ 物体i++模拟——6 7 8 9 10 11j = 11 size = 5 dp[6]*/bool wordBreak(string s, vector<string>& wordDict) {dp[0] = 1;bool tmp[100][100];for(int j = 0; j <= s.size();j++){for(int i = 0; i < wordDict.size();i++){if(j == wordDict[i].size())  // 能装下一个dp[j] =  (s.substr(j  - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];else if(j > wordDict[i].size() )    // 能至少装2个 dp[j] = dp[j  - wordDict[i].size()] && (s.substr(j - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];}}// for(int i = 0; i < wordDict.size();i++)// {//     for(int j = 0; j < s.size();j++)//         cout << tmp[i][j] << ' ';//     cout << endl;// }return dp[s.size() ];}
};

2 多重背包

感觉考的不多,算法笔记也没有,看看理论。

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用,每件耗费的空间是Ci ,价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大。

解法1:每件物品最多有Mi件可用,把Mi件摊开,其实就是一个01背包问题了。

解法2:解法1上优化(神奇优化方式–二进制+拆包(具体过程见笔记本))

3 背包总结

from

相关文章:

代码随想录打卡—day46—【DP】— 8.29 背包END

1 139. 单词拆分 139. 单词拆分 做了很久...估计2h 一开始我的思路卡死了 看题解之后的思路的详解见注释&#xff0c; 我的写法和carl 答案在一些微小的细节上略有不同&#xff0c;我的更好理解&#xff0c;但他的解法更简单。 我写的过程中&#xff0c;需要注意下标和字符…...

lua学习-3 循环和流程控制

这里写目录标题 判断for 循环数值遍历泛型遍历遍历数组遍历对象ipairs 和 pairs的异同 while 循环repeat循环goto基础用法注意事项 判断 for 循环 数值遍历 for exp1,exp2,exp3 do//todoend上述代码是指&#xff1a;从exp1 到exp2 以exp3为步长进行循环并执行todo代码&#…...

3、监测数据采集物联网应用开发步骤(3)

监测数据采集物联网应用开发步骤(2) 系统整体结构搭建 新建项目 输入项目名称&#xff1a;MonitorData 所谓兵马未动粮草先行&#xff0c;按下图创建好对应的模块备用&#xff1a; com.plugins 业务插件模块 com.zxy.adminlog 日志或文本文…...

MySQL用户管理及用户权限

目录 数据库用户管理 新建用户 查看用户 重命名用户rename 删除用户drop 修改用户密码 找回root密码 数据库用户授权 授予权限 查看用户权限 撤销用户权限 数据库用户管理 新建用户 CREATE USER 用户名来源地址 [IDENTIFIED BY [PASSWORD] 密码];用户名&#xff1a…...

Yolov8-pose关键点检测:模型轻量化创新 | PConv结合c2f | CVPR2023 FasterNet

💡💡💡本文解决什么问题:新的partial convolution(PConv),通过同时减少冗余计算和内存访问可以更有效地提取空间特征。 PConv| GFLOPs从9.6降低至8.5,参数量从6482kb降低至6134kb, mAP50从0.921提升至0.925 Yolov8-Pose关键点检测专栏介绍:https://blog.csdn.n…...

聊聊mybatis-plus的SafetyEncryptProcessor

序 本文主要研究一下mybatis-plus的SafetyEncryptProcessor SafetyEncryptProcessor mybatis-plus-boot-starter/src/main/java/com/baomidou/mybatisplus/autoconfigure/SafetyEncryptProcessor.java public class SafetyEncryptProcessor implements EnvironmentPostProc…...

【PCL (Point Cloud Library)可视化点云的工具汇总】

PCL (Point Cloud Library)可视化点云的工具 PCL (Point Cloud Library) 提供了一系列的工具和类用于点云的可视化。以下是其中的一些主要工具和功能: pcl::visualization::CloudViewer: 如前所述,这是一个简单易用的可视化工具,主要用于基本的点云显示。pcl::visualizatio…...

实现 Trie (前缀树)

题目链接 实现 Trie (前缀树) 题目描述 注意点 word 和 prefix 仅由小写英文字母组成 解答思路 首先要理解前缀树是什么&#xff0c;参照该篇文章【图解算法】模板变式——带你彻底搞懂字典树(Trie树)在了解前缀树是什么后&#xff0c;设计前缀树就会更加容易&#xff0c;…...

ElasticSearch基础知识汇总

文章目录 前言一、认识ElasticSearch1.正向索引和倒排索引2. MySql与ElasticSearc3.IK分词器 二、ES索引库操作1.mapping映射属性2.索引库的CRUD 三、ES文档库操作 前言 Elasticsearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎&#xff0c;基…...

服务器数据库中了locked勒索病毒怎么办,locked勒索病毒恢复工具

最近一段时间网络上的locked勒索病毒非常嚣张&#xff0c;自从6月份以来&#xff0c;很多企业的计算机服务器数据库遭到了locked勒索病毒的攻击&#xff0c;起初locked勒索病毒攻击用友畅捷通T用户&#xff0c;后来七月份开始攻击金蝶云星空客户&#xff0c;导致企业的财务系统…...

没有 JavaScript 计时器的自动播放轮播 - CSS 动画

先看效果&#xff1a; 再看代码&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>计时器</title><style>* {padding: 0;margin: 0;box-siz…...

《Flink学习笔记》——第三章 Flink的部署模式

不同的应用场景&#xff0c;有时候对集群资源的分配和占用有不同的需求。所以Flink为各种场景提供了不同的部署模式。 3.1 部署模式&#xff08;作业角度/通用分类&#xff09; 根据集群的生命周期、资源的分配方式、main方法到底在哪里执行——客户端还是Client还是JobManage…...

网络安全(黑客技术)0基础学习手册

目录梗概 一、自学网络安全学习的误区和陷阱 二、学习网络安全的一些前期准备 三、网络安全学习路线 四、学习资料的推荐 想自学网络安全&#xff08;黑客技术&#xff09;首先你得了解什么是网络安全&#xff01;什么是黑客&#xff01; 网络安全可以基于攻击和防御视角来…...

腾讯云服务器价格表大全_轻量服务器_CVM云服务器报价明细

腾讯云服务器租用费用表&#xff1a;轻量应用服务器2核2G4M带宽112元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、云服务器CVM S5实例2核2G配置280.8元一年、GPU服务器GN10Xp实例145元7天&#xff0c;腾讯云服务器网长期更新腾讯云轻量…...

vue中bus的使用和涉及到的问题

创建一个js文件 import Vue from "Vue" export default new Vue 我们可以直接在要使用的页面中引用使用 import bus from /assets/js/eventBus.js;bus.$emit("info", "123") // 使用bus.$on("info", (val) > { // 接收console.l…...

Flink的简要概述

以下是Flink的各种架构的简要概述&#xff1a; 1. Flink概述&#xff1a;Apache Flink是一个开源的流处理和批处理框架&#xff0c;具有高性能、容错性和数据一致性保证。它支持事件驱动的流处理和批量处理&#xff0c;并提供了丰富的API和工具来处理实时数据流和大规模数据集…...

多线程下的signal信号处理

多线程中&#xff0c;信号在哪个线程中处理是不确定的&#xff0c;可能被任意一个线程处理 下边的代码可以验证该结论&#xff0c;多次Ctrlc&#xff0c;会被不同的线程捕获此信号&#xff0c;并处理&#xff0c;最终每个线程死锁&#xff0c;阻塞在等待锁的状态 #include &l…...

〖Python网络爬虫实战㉞〗- 图形验证码OCR识别

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;订阅本专栏前必读关于专栏〖Python网络爬虫实战〗转为付费专栏的订阅说明作者&#xff1…...

Python Scrapy网络爬虫框架从入门到实战

Python Scrapy是一个强大的网络爬虫框架&#xff0c;它提供了丰富的功能和灵活的扩展性&#xff0c;使得爬取网页数据变得简单高效。本文将介绍Scrapy框架的基本概念、用法和实际案例&#xff0c;帮助你快速上手和应用Scrapy进行数据抓取。 Scrapy是一个基于Python的开源网络爬…...

后端面试话术集锦第四篇:ElasticSearch面试话术

🚗后端面试集锦目录 💖后端面试话术集锦第 1 篇:spring面试话术💖 💖后端面试话术集锦第 2 篇:spring boot面试话术💖 💖后端面试话术集锦第 3 篇:spring cloud面试话术💖 💖后端面试话术集锦第 4 篇:ElasticSearch面试话术💖 💖后端面试话术集锦第 5 …...

JiYuTrainer学习自由解决方案:重新定义课堂自主权的教育技术工具

JiYuTrainer学习自由解决方案&#xff1a;重新定义课堂自主权的教育技术工具 【免费下载链接】JiYuTrainer 极域电子教室防控制软件, StudenMain.exe 破解 项目地址: https://gitcode.com/gh_mirrors/ji/JiYuTrainer 你还记得那种感觉吗&#xff1f;当老师在讲台上演示关…...

3分钟上手QrazyBox:让损坏的二维码“起死回生“的终极修复工具

3分钟上手QrazyBox&#xff1a;让损坏的二维码"起死回生"的终极修复工具 【免费下载链接】qrazybox QR Code Analysis and Recovery Toolkit 项目地址: https://gitcode.com/gh_mirrors/qr/qrazybox 你是否曾经遇到过这样的场景&#xff1a;打印出来的二维码被…...

5分钟快速上手:LuckyLilliaBot QQ机器人完整部署指南

5分钟快速上手&#xff1a;LuckyLilliaBot QQ机器人完整部署指南 【免费下载链接】LuckyLilliaBot 支持 OneBot 11、Satori 和 Milky 协议 项目地址: https://gitcode.com/gh_mirrors/li/LuckyLilliaBot 你是否正在寻找一款简单易用、功能强大的QQ机器人框架&#xff1f…...

Ganache 快速启动与 Truffle 项目集成实战

1. 为什么选择Ganache作为开发起点 刚接触区块链开发时&#xff0c;最头疼的就是如何在本地快速搭建测试环境。以太坊主网不仅需要真实ETH&#xff0c;每笔交易还要等待区块确认&#xff0c;完全不适合开发调试。这时候Ganache就像个贴心的开发助手&#xff0c;它能在本地一键生…...

从零到一:RK3588s平台imx415双目相机模组点亮与ISP调优实战

1. 环境准备&#xff1a;从零搭建开发环境 第一次接触RK3588s平台时&#xff0c;最头疼的就是环境搭建。我用的Firefly AIO-3588S-JD4开发板配套资料比较分散&#xff0c;光是找齐所有软件包就花了半天时间。这里分享下我的踩坑经验&#xff1a; 硬件清单必须严格核对&#x…...

从点灯到项目:手把手教你为TMS320F28335创建可复用的工程模板

从点灯到项目&#xff1a;手把手教你为TMS320F28335创建可复用的工程模板 当你第一次点亮TMS320F28335开发板上的LED时&#xff0c;那种成就感无与伦比。但很快你会发现&#xff0c;随着项目复杂度提升&#xff0c;代码开始变得混乱不堪——头文件散落各处、函数命名随意、每次…...

为什么92%的团队把DeepSeek CQRS配错了?资深SRE曝光3个被文档刻意弱化的配置陷阱

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;为什么92%的团队把DeepSeek CQRS配错了&#xff1f;资深SRE曝光3个被文档刻意弱化的配置陷阱 陷阱一&#xff1a;事件序列号&#xff08;Sequence ID&#xff09;与数据库事务隔离级别的隐式冲突 Deep…...

Klaxon与Jackson对比:选择最适合你的Kotlin JSON解析器

Klaxon与Jackson对比&#xff1a;选择最适合你的Kotlin JSON解析器 【免费下载链接】klaxon A JSON parser for Kotlin 项目地址: https://gitcode.com/gh_mirrors/kl/klaxon 在Kotlin开发中&#xff0c;JSON解析是处理数据交换的核心任务之一。Klaxon作为一款专为Kotli…...

别再怕Windows桌面软件测试了!用Python+UIAutomation手把手搭建自动化框架(附完整源码)

从零构建Windows GUI自动化测试框架&#xff1a;Python与UIAutomation实战指南 Windows桌面应用的自动化测试常被视为测试领域的"硬骨头"&#xff0c;但当你拆解其核心逻辑后&#xff0c;会发现它与你熟悉的Web自动化测试有着惊人的相似架构。本文将彻底打破技术恐惧…...

WandEnhancer终极指南:3步解锁完整WeMod高级功能

WandEnhancer终极指南&#xff1a;3步解锁完整WeMod高级功能 【免费下载链接】Wand-Enhancer Advanced UX and interoperability extension for Wand (WeMod) app 项目地址: https://gitcode.com/gh_mirrors/we/Wand-Enhancer 还在为WeMod高级功能付费而烦恼吗&#xff…...