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

代码随想录训练营二刷第四十八天 | 139.单词拆分 背包问题总结

代码随想录训练营二刷第四十八天 | 139.单词拆分 背包问题总结

一、139.单词拆分

题目链接:https://leetcode.cn/problems/word-break/
思路:单词拼字符串,完全背包。定义dp[i],为true表示可以拆分为一或多个单词。可能会出现aba的情况,字典{a, b},所以是排列数,背包在外,物品在内。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] valid = new boolean[s.length() + 1];valid[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !valid[i]; j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}
}

二、背包问题总结

背包问题:一维数组,dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。

01背包遍历顺序:先物品后背包,物品正序,背包逆序。

如若背包正序则会出现同一个物品重复放入,如物品1重量为1,背包空间为1时放入了,背包空间为2时又放入了。
如果先背包后物品,为了避免重复放入背包依然是逆序,背包容量固定时,每种背包容量只能放入一个物品,即为最大的物品,小的物品都放不进来或者被覆盖了。

求组合数排列数:dp[j] += dp[j - nums[i]]

完全背包遍历顺序:物品背包没有先后顺序,物品背包都是正序。因为同一个物品不限量可以放入多次,在背包采用正序中。

完全背包求组合数,物品在外,背包在内。求排列数,背包在外,物品在内。

相关文章:

代码随想录训练营二刷第四十八天 | 139.单词拆分 背包问题总结

代码随想录训练营二刷第四十八天 | 139.单词拆分 背包问题总结 一、139.单词拆分 题目链接&#xff1a;https://leetcode.cn/problems/word-break/ 思路&#xff1a;单词拼字符串&#xff0c;完全背包。定义dp[i]&#xff0c;为true表示可以拆分为一或多个单词。可能会出现ab…...

【数据挖掘】2017年 Quiz 1-3 整理 带答案

目录 Quiz 1Quiz 2Quiz 3Quiz 1 Answer Problems 1-2 based on the following training set, where A , B , C A, B, C A,B,</...

吃鸡高手必备工具大揭秘!提高战斗力,分享干货,一站满足!

大家好&#xff01;你是否想提高吃鸡游戏的战斗力&#xff0c;分享顶级的游戏作战干货&#xff0c;方便进行吃鸡作图和查询装备皮肤库存&#xff1f;是否也担心被骗&#xff0c;希望查询游戏账号是否在黑名单上&#xff0c;或者查询失信人和VAC封禁情况&#xff1f;在这段视频中…...

集群化环境前置准备

目录 部署 1. 配置多台Linux虚拟机 1.1 首先&#xff0c;关机当前CentOS系统虚拟机&#xff08;可以使用root用户执行init 0来快速关 机&#xff09; 1.2 新建文件夹 1.3 克隆 1.4 同样的操作克隆出&#xff1a;node2和node3 1.5 开启node1&#xff0c;修改主机名为node1&…...

nodejs开发环境搭建

Nodejs是一个开源的、跨平台JavaScript运行时环境&#xff0c;其使用V8引擎对JavaScript脚本执行解释&#xff0c;在前后端分离的应用架构设计中&#xff0c;其既能支持web页面服务应用的开发、也能支持后端接口服务应用的开发&#xff0c;类似于Java语言的J2EE运行时环境&…...

C语言qsort函数

排序qsort int int cmp(const void *a, const void *b) {return *(int *)a - *(int *)b;//先强转成int型&#xff0c;后解引用取值比较大小 }字符串数组 char a[] “hello world” //字符串数组&#xff0c;存放的是字符 int cmp(const void *a, const void *b) {return *(…...

如何使用 Hotshot 通过文字生成 GIF 动画

Hotshot 是一个基于人工智能的工具&#xff0c;可用于通过文字生成 GIF 动画。该工具使用最新的图像生成技术来创建逼真的动画&#xff0c;即使是复杂的文字描述也能做到。 hotshot访问地址 使用 Hotshot 生成 GIF 动画 要使用 Hotshot 生成 GIF 动画&#xff0c;您需要首先…...

吃鸡高手必备!这些技巧帮你提高战斗力!

大家好&#xff01;作为一名吃鸡玩家&#xff0c;我们都想提高自己的战斗力&#xff0c;享受顶级游戏作战干货&#xff0c;装备皮肤库存展示和查询&#xff0c;并避免被骗游戏账号。在这里&#xff0c;我将为大家介绍一些实用的技巧和工具&#xff0c;让你成为吃鸡高手&#xf…...

XV6 操作系统实验

环境搭建 ubuntu 新建一个文件setup.sh&#xff0c;内容如下 #获取工具链 git clone --recursive https://github.com/riscv/riscv-gnu-toolchain #安装必要依赖 sudo apt-get update sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev li…...

leetcode - 双周赛114

一&#xff0c;2869.收集元素的最小操作次数 // 解法&#xff1a;哈希表 从右往左遍历 class Solution {public int minOperations(List<Integer> nums, int k) {Set<Integer> set new HashSet<>();for(int i1; i<k; i){set.add(i);}for(int inums.size…...

【LeetCode刷题笔记】双指针

剑指 Offer 21.调整数组顺序使奇数位于偶数前面 解题思路&#xff1a; 对撞指针 &#xff0c; 从左边不停的找第一个偶数&#xff0c;从右边不停的找第一个奇数 &#xff0c;找到后 交换 两者位置 本题与【905. 按奇偶排序数组】几乎雷同。 剑指 Offer 57.和为s的两个数字 本题…...

互联网Java工程师面试题·Memcached 篇·第二弹

目录 10、memcached 如何实现冗余机制&#xff1f; 11、memcached 如何处理容错的&#xff1f; 12、如何将 memcached 中 item 批量导入导出&#xff1f; 13、如果缓存数据在导出导入之间过期了&#xff0c;您又怎么处理这些数据呢&#xff1f; 14、memcached 是如何做身份…...

特斯拉被称为自动驾驶领域的苹果

特斯拉的自动驾驶技术无疑是居于世界上领先地位的,有人形容特斯拉是自动驾驶汽车领域的苹果。特斯拉发布的Tesla Vision系统只配备了摄像头,不依靠雷达。 这并不是特斯拉唯一和其它对手不同的地方,他们的整个战略都是基于车队和销售产品,而其大多数竞争对手则销售自…...

stm32之HAL库操作PAJ75620

一、模块简介 手势模块PAJ7620主要利用IIC或SPI协议来实现数据的传输&#xff0c;本实验用的模块是以IIC来进行信息传输。支持电压从2.8v到3.6v, 正常可以选择3.3v。检测的距离从5到15cm, 可以检测9种手势&#xff0c;包括 右&#xff1a;编码为 0x01左&#xff1a;编码为 0x0…...

医学影像归档与通讯系统(PACS)系统源码 PACS三维图像后处理技术

医学影像归档与通讯系统&#xff08;PACS&#xff09;系统源码 PACS三维图像处理 医学影像归档与通讯系统&#xff08;PACS&#xff09;系统&#xff0c;是一套适用于从单一影像设备到放射科室、到全院级别等各种应用规模的医学影像归档与通讯系统。PACS集患者登记、图像采集、…...

web漏洞-PHP反序列化

目录 PHP反序列化序列化反序列化原理涉及技术利用危害CTF靶场 PHP反序列化 序列化 将对象转换成字符串 反序列化 相反&#xff0c;将字符串转换成对象。 数据格式的转换对象的序列化有利于对象的保存和传输&#xff0c;也可以让多个文件共享对象。 原理 未对用户输入的序列化字…...

Redis-分布式锁

分布式锁相关内容 超卖问题切入可以使用互斥锁给先获取到锁的线程加锁吗&#xff1f;使用redis分布式锁解决超卖问题setnx命令实现分布式锁为什么需要设置过期时间&#xff1f;Redis实现分布式锁如何合理控制锁的有效时长 redisson实现分布式锁 超卖问题切入 我们先来看一个项目…...

什么时候使用继承,好莱坞原则(设计模式与开发实践 P11+)

文章目录 好莱坞原则真的需要继承吗&#xff1f; 好莱坞原则 如果你熟悉继承方法、乃至模板方法模式后&#xff0c;就可以了解一个设计原则 好莱坞原则 新人演员把简历发给好莱坞&#xff0c;许久之后没有回应不耐烦打电话给好莱坞&#xff0c;只收到回应&#xff1a;不要来找…...

蓝桥等考Python组别十四级001

第一部分&#xff1a;选择题 1、Python L14 &#xff08;15分&#xff09; 运行下面程序&#xff0c;输出的结果是&#xff08; &#xff09;。 d {A: 501, B: 602, C: 703, D: 804} print(d[B]) 501602703804 正确答案&#xff1a;B 2、Python L14 &#xff08;15分…...

TI单芯片毫米波雷达代码走读(二十七)—— 角度维(3D)处理之通道间幅相一致性补偿

TI单芯片毫米波雷达1642代码走读(〇)——总纲 书接上回,我们知晓了3D处理的主要流程,相信大家都已理解基本的原理。在正式进行数据分析之前还有一步关键的步骤需要说明,即通道间的幅相一致性补偿问题。 细心的朋友可能注意到,在3D处理的的原码中有两个函数我一直没有讲:…...

Claude推理接口低延迟优化秘技:FastAPI异步中间件+缓存穿透防护+请求批处理(仅限内部团队泄露版)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Claude推理接口低延迟优化秘技&#xff1a;FastAPI异步中间件缓存穿透防护请求批处理&#xff08;仅限内部团队泄露版&#xff09; 核心瓶颈定位 Claude官方API在高并发场景下常出现P99延迟飙升至1.2…...

Java 开发 - Java 静态方法调用类初始化规则观察记录

Java 静态方法调用类初始化规则观察记录 1、基本介绍 静态方法调用不会触发子类的初始化&#xff0c;只会触发声明该方法的类及其父类的初始化 2、观察记录 &#xff08;1&#xff09;测试 1 public class CommonStore {static {System.out.println("CommonStore static e…...

EPLAN浮动许可利用率低:软件许可浪费,解决许可不足

EPLAN浮动许可利用率低&#xff1f;别再浪费了&#xff01;你是不是也遇到过这种事&#xff1a;新项目启动前看许可证池还有几个名额&#xff0c;结果发现上个月的几个许可证一直在等&#xff1f;我就踩了这个坑&#xff0c;发现公司用EPLAN的几个项目组天天在"抢"许…...

环境配置与基础教程:梯度累积技术落地:在显存受限条件下用梯度累积模拟大 batch 训练,精度无损

引言:当显卡“钱包”不够鼓,我们如何训练大模型? 2025年底到2026年初的AI开发者社区里,一个反复被追问的问题是:“我用RTX 3060/4060(12GB显存)能微调LLaMA-7B吗?”另一个高赞回答总会提到同一个关键词——梯度累积(Gradient Accumulation)。根据CSDN技术社区2026年…...

三月七小助手:星穹铁道自动化工具如何帮你每天节省30分钟游戏时间

三月七小助手&#xff1a;星穹铁道自动化工具如何帮你每天节省30分钟游戏时间 【免费下载链接】March7thAssistant 崩坏&#xff1a;星穹铁道全自动 三月七小助手 项目地址: https://gitcode.com/gh_mirrors/ma/March7thAssistant 你是否每天花费大量时间在《崩坏&#…...

TypeScript领域建模实战:基于斯坦福本体论七步法构建健壮数据模型

1. 项目概述如果你和我一样&#xff0c;在TypeScript项目里摸爬滚打了几年&#xff0c;肯定遇到过这样的场景&#xff1a;面对一个全新的业务领域&#xff0c;老板让你“设计一下数据模型”&#xff0c;你打开一个空白的types.ts文件&#xff0c;光标闪烁&#xff0c;大脑一片空…...

AI驱动终端交互:用自然语言指挥命令行的新范式

1. 项目概述&#xff1a;一个AI驱动的终端交互新范式最近在终端工具圈里&#xff0c;一个名为“yai”的项目引起了我的注意。它不是一个简单的命令行美化工具&#xff0c;也不是一个传统的终端复用器。简单来说&#xff0c;yai是一个由 AI 驱动的、旨在彻底改变你与终端交互方式…...

从淘宝几块钱的2804云台电机开始,手把手教你DIY一个桌面机械臂关节(STM32/GD32 + SimpleFOC)

从零打造低成本机械臂关节&#xff1a;2804云台电机FOC控制实战指南 在创客圈里&#xff0c;机械臂项目总是让人既向往又却步——商用伺服电机动辄上千元的单价&#xff0c;让许多爱好者望而却步。但当我发现淘宝上仅售几元的2804云台电机时&#xff0c;一个大胆的想法诞生了&a…...

mysql数据库响应缓慢如何排查_使用EXPLAIN分析执行计划

type为ALL表示全表扫描&#xff0c;说明MySQL未使用索引&#xff1b;若rows接近总行数且Extra含Using where但无Using index&#xff0c;则索引失效。应检查WHERE字段是否建索引、遵循联合索引最左匹配、确保类型一致、避免索引列上函数操作。EXPLAIN 显示 type 是 ALL&#xf…...

德克萨斯大学奥斯汀分校研究出新型“轻量级“数据压缩神经网络

这项由德克萨斯大学奥斯汀分校系统机器学习实验室完成的研究&#xff0c;以预印本形式于2026年5月7日发布在arXiv平台&#xff0c;论文编号为arXiv:2605.06628&#xff0c;研究方向属于信号处理与深度学习的交叉领域。有兴趣深入了解的读者可以通过上述编号在arXiv上检索完整论…...