代码随想录算法训练营第四十六天| 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大模型于近期面世,它能让机器人学习互联网上的文本和图像,并具备逻辑推理能力。 该模型为机器人智能带来显著升级…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
