代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结
代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结
一、力扣139.单词拆分
题目链接:
思路:确定dp数组,dp[i]为true表示从0到i切分的字串都在字典中出现过。
确定递推公式,dp[i] 为true要求 s[j, i] 在字典中出现,且dp[j]为true,即可设置dp[i]=true
初始化,dp[0]=true,这个设置为true是为了让后面依赖前面的状态。
遍历时注意,字典中的单词可以在s的前面出现也可以在后面出现,这就是排列问题,单组合物品在前面出现就不会在后面出现。另外注意substring是左闭右开。
class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] dp = new boolean[s.length()+1];dp[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !dp[i]; j++) {if (set.contains(s.substring(j, i)) && dp[j]) {dp[i] = true;}}}return dp[s.length()];}
}
二、背包问题总结
背包五部曲:
1、确定dp数组(dp table)以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组
背包递推公式
问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
问装满背包有几种方法: dp[j] += dp[j - nums[i]]
问背包装满最大价值: dp[j] = max(dp[j], dp[j - weight[me]] + value[me]);
问装满背包所有物品的最小个数: dp[j] = min(dp[j - coins[me]] + 1, dp[j]);
遍历顺序
01背包
二维数组的01背包,先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。
一维dp数组的01背包,只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。
完全背包
一维dp数组的完全背包,先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
如果求最小数,那么两层for循环的先后顺序就无所谓了
相关文章:
代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结
代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结 一、力扣139.单词拆分 题目链接: 思路:确定dp数组,dp[i]为true表示从0到i切分的字串都在字典中出现过。 确定递推公式,dp[i] 为true要求 s[j, i] 在字典中出现&…...
【机器学习】西瓜书习题3.3Python编程实现对数几率回归
参考代码 结合自己的理解,添加注释。 代码 导入相关的库 import numpy as np import pandas as pd import matplotlib from matplotlib import pyplot as plt from sklearn import linear_model导入数据,进行数据处理和特征工程 # 1.数据处理&#x…...
Blazor前后端框架Known-V1.2.9
V1.2.9 Known是基于C#和Blazor开发的前后端分离快速开发框架,开箱即用,跨平台,一处代码,多处运行。 Gitee: https://gitee.com/known/KnownGithub:https://github.com/known/Known 概述 基于C#和Blazor…...
【3D捏脸功能实现】
文章目录 一、技术方案介绍二、技术核心三、底层技术实现选型进行模型建模编写逻辑代码 四、功能落地五、总结 一、技术方案介绍 3D捏脸功能是一种利用3D技术实现用户自定义头像的功能。通常实现这种功能需要以下技术: 3D建模技术。通过3D建模技术可以创建一个可以…...
Kafka的零拷贝
传统的IO模型 如果要把磁盘中的某个文件发送到远程服务器需要经历以下几个步骤 (1) 从磁盘中读取文件的内容,然后拷贝到内核缓冲区 (2) CPU把内核缓冲区的数据赋值到用户空间的缓冲区 (3) 在用户程序中调用write方法,把用户缓冲区的数据拷贝到内核下面…...
如何使用Python进行数据分析?
Python是一个非常流行的编程语言,也是数据科学家和数据分析师最常用的语言之一。 Python的生态系统非常丰富,有很多强大的库和工具可以用来进行数据分析,如NumPy、Pandas、Matplotlib、SciPy等。 Python教程,8天python从入门到精…...
概率论与数理统计复习总结3
概率论与数理统计复习总结,仅供笔者复习使用,参考教材: 《概率论与数理统计》/ 荣腾中主编. — 第 2 版. 高等教育出版社《2024高途考研数学——概率基础精讲》王喆 概率论与数理统计实际上是两个互补的分支:概率论 在 已知随机…...
PHP正则绕过解析
正则绕过 正则表达式PHP正则回溯PHP中的NULL和false回溯案例案例1案例2 正则表达式 在正则中有许多特殊的字符,不能直接使用,需要使用转义符\。如:$,(,),*,,.,?,[,,^,{。 这里大家会有疑问:为啥小括号(),这个就需要两个来转义&a…...
Hive巡检脚本
Hive巡检脚本的示例: #!/bin/bash# 设置Hive连接信息 HIVE_HOST"your_hive_host" HIVE_PORT"your_hive_port" HIVE_USER"your_hive_username" HIVE_PASSWORD"your_hive_password"# 设置巡检结果输出文件路径 OUTPUT_FILE&…...
【状态估计】基于UKF法、AUKF法的电力系统三相状态估计研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
webpack复习
webpack webpack复习 webpack基本配置 拆分配置 - 公共配置 生产环境配置 开发环境配置 使用merge webpack-dev-server 启动本地服务 在公共中引入babel-loader处理es6 webpack高级配置 多入口文件 enty 入口为一个对象 里面的key为入口名 value为入口文件路径 例如 pa…...
开始学习 Kafka,一文掌握基本概念|Kafka 系列 一
如果你还不了解 Kafka,或者也打算深入探索、系统学习,那么欢迎有同样目标的小伙伴可以加群交流,让学习之路不再孤独。 一个人可能走的很快,但是一群人会走的更远。(后台回复:加群) 点击上方“后…...
Couldn‘t lock the file :/tmp/bbc-filesystem-base_syscache_service
解决方案: 进去带这个目录,然后切换成root用户,将它删除...
vscode 通过mongoose 连接mongodb atlas
了解mongodb 的项目结构 1.代表集群名称 > 2.代表数据库名称>3.代表每个 collection名称 三者范围为从大到小的关系 (一对多)。每个集群有不同的连接地址、用户信息(Database Access)、ip配置信息(Network Acce…...
记录 Vue3 + Ts 类型使用
阅读时长: 10 分钟 本文内容:记录在 Vue3 中使用 ts 时的各种写法. 类型大小写 vue3 ts 项目中,类型一会儿大写一会儿小写。 怎么区分与基础类型使用? String、string、Number、number、Boolean、boolean … 在 js 中, 以 string 与 String…...
主从同步带来的业务问题
目录 一: 目前的业务问题二:如何平衡主从不同步和业务隔离?三:解决方案 一: 目前的业务问题 业务A会跑一些规则, 跑完会把规则结果信息落地(落地到主库), 然后会通过TDM…...
主动带宽控制工具
停机和带宽过度使用是任何组织都无法避免的两个问题。随着企业采用 BYOD 文化,通过网络的流量负载可能很重,导致网络拥塞并使网络容易受到网络攻击。为了解决这个问题,企业需要全面的监控策略来保护网络,当看似大量的流量进入网络…...
数据采集的方法有哪些?
近年来,国家和各大企业都在部署大数据战略。“大数据”这个词也越来越频繁地出现在我们的生活中。当我们在进行网上冲浪时,页面总会跳出我们想要搜索的相关产品或关联事物。大数据,似乎总是能够“算”出我们“心中所想”。那么,大…...
linux重新学习-纪录篇
前言: 正式学习linux的时候,除了那些命令之外,更多的是对于这个系统的重新认知。 linux的身世? 在上世纪90年代,那时候计算机非常的珍贵,配置也很一般般,系统也贵,所以没啥人用,在当…...
为机器人装“大脑” 谷歌发布RT-2大模型
大语言模型不仅能让应用变得更智能,还将让机器人学会举一反三。在谷歌发布RT-1大模型仅半年后,专用于机器人的RT-2大模型于近期面世,它能让机器人学习互联网上的文本和图像,并具备逻辑推理能力。 该模型为机器人智能带来显著升级…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
