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

代码随想录算法训练营第四十六天| 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.单词拆分 题目链接&#xff1a; 思路&#xff1a;确定dp数组&#xff0c;dp[i]为true表示从0到i切分的字串都在字典中出现过。 确定递推公式&#xff0c;dp[i] 为true要求 s[j, i] 在字典中出现&…...

【机器学习】西瓜书习题3.3Python编程实现对数几率回归

参考代码 结合自己的理解&#xff0c;添加注释。 代码 导入相关的库 import numpy as np import pandas as pd import matplotlib from matplotlib import pyplot as plt from sklearn import linear_model导入数据&#xff0c;进行数据处理和特征工程 # 1.数据处理&#x…...

Blazor前后端框架Known-V1.2.9

V1.2.9 Known是基于C#和Blazor开发的前后端分离快速开发框架&#xff0c;开箱即用&#xff0c;跨平台&#xff0c;一处代码&#xff0c;多处运行。 Gitee&#xff1a; https://gitee.com/known/KnownGithub&#xff1a;https://github.com/known/Known 概述 基于C#和Blazor…...

【3D捏脸功能实现】

文章目录 一、技术方案介绍二、技术核心三、底层技术实现选型进行模型建模编写逻辑代码 四、功能落地五、总结 一、技术方案介绍 3D捏脸功能是一种利用3D技术实现用户自定义头像的功能。通常实现这种功能需要以下技术&#xff1a; 3D建模技术。通过3D建模技术可以创建一个可以…...

Kafka的零拷贝

传统的IO模型 如果要把磁盘中的某个文件发送到远程服务器需要经历以下几个步骤 (1) 从磁盘中读取文件的内容&#xff0c;然后拷贝到内核缓冲区 (2) CPU把内核缓冲区的数据赋值到用户空间的缓冲区 (3) 在用户程序中调用write方法&#xff0c;把用户缓冲区的数据拷贝到内核下面…...

如何使用Python进行数据分析?

Python是一个非常流行的编程语言&#xff0c;也是数据科学家和数据分析师最常用的语言之一。 Python的生态系统非常丰富&#xff0c;有很多强大的库和工具可以用来进行数据分析&#xff0c;如NumPy、Pandas、Matplotlib、SciPy等。 Python教程&#xff0c;8天python从入门到精…...

概率论与数理统计复习总结3

概率论与数理统计复习总结&#xff0c;仅供笔者复习使用&#xff0c;参考教材&#xff1a; 《概率论与数理统计》/ 荣腾中主编. — 第 2 版. 高等教育出版社《2024高途考研数学——概率基础精讲》王喆 概率论与数理统计实际上是两个互补的分支&#xff1a;概率论 在 已知随机…...

PHP正则绕过解析

正则绕过 正则表达式PHP正则回溯PHP中的NULL和false回溯案例案例1案例2 正则表达式 在正则中有许多特殊的字符&#xff0c;不能直接使用&#xff0c;需要使用转义符\。如&#xff1a;$,(,),*,,.,?,[,,^,{。 这里大家会有疑问&#xff1a;为啥小括号(),这个就需要两个来转义&a…...

Hive巡检脚本

Hive巡检脚本的示例&#xff1a; #!/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代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

webpack复习

webpack webpack复习 webpack基本配置 拆分配置 - 公共配置 生产环境配置 开发环境配置 使用merge webpack-dev-server 启动本地服务 在公共中引入babel-loader处理es6 webpack高级配置 多入口文件 enty 入口为一个对象 里面的key为入口名 value为入口文件路径 例如 pa…...

开始学习 Kafka,一文掌握基本概念|Kafka 系列 一

如果你还不了解 Kafka&#xff0c;或者也打算深入探索、系统学习&#xff0c;那么欢迎有同样目标的小伙伴可以加群交流&#xff0c;让学习之路不再孤独。 一个人可能走的很快&#xff0c;但是一群人会走的更远。&#xff08;后台回复&#xff1a;加群&#xff09; 点击上方“后…...

Couldn‘t lock the file :/tmp/bbc-filesystem-base_syscache_service

解决方案&#xff1a; 进去带这个目录&#xff0c;然后切换成root用户&#xff0c;将它删除...

vscode 通过mongoose 连接mongodb atlas

了解mongodb 的项目结构 1.代表集群名称 > 2.代表数据库名称>3.代表每个 collection名称 三者范围为从大到小的关系 &#xff08;一对多&#xff09;。每个集群有不同的连接地址、用户信息&#xff08;Database Access&#xff09;、ip配置信息&#xff08;Network Acce…...

记录 Vue3 + Ts 类型使用

阅读时长: 10 分钟 本文内容&#xff1a;记录在 Vue3 中使用 ts 时的各种写法. 类型大小写 vue3 ts 项目中&#xff0c;类型一会儿大写一会儿小写。 怎么区分与基础类型使用? String、string、Number、number、Boolean、boolean … 在 js 中&#xff0c; 以 string 与 String…...

主从同步带来的业务问题

目录 一&#xff1a; 目前的业务问题二&#xff1a;如何平衡主从不同步和业务隔离&#xff1f;三&#xff1a;解决方案 一&#xff1a; 目前的业务问题 业务A会跑一些规则&#xff0c; 跑完会把规则结果信息落地&#xff08;落地到主库&#xff09;&#xff0c; 然后会通过TDM…...

主动带宽控制工具

停机和带宽过度使用是任何组织都无法避免的两个问题。随着企业采用 BYOD 文化&#xff0c;通过网络的流量负载可能很重&#xff0c;导致网络拥塞并使网络容易受到网络攻击。为了解决这个问题&#xff0c;企业需要全面的监控策略来保护网络&#xff0c;当看似大量的流量进入网络…...

数据采集的方法有哪些?

近年来&#xff0c;国家和各大企业都在部署大数据战略。“大数据”这个词也越来越频繁地出现在我们的生活中。当我们在进行网上冲浪时&#xff0c;页面总会跳出我们想要搜索的相关产品或关联事物。大数据&#xff0c;似乎总是能够“算”出我们“心中所想”。那么&#xff0c;大…...

linux重新学习-纪录篇

前言&#xff1a; 正式学习linux的时候&#xff0c;除了那些命令之外&#xff0c;更多的是对于这个系统的重新认知。 linux的身世? 在上世纪90年代&#xff0c;那时候计算机非常的珍贵&#xff0c;配置也很一般般&#xff0c;系统也贵&#xff0c;所以没啥人用&#xff0c;在当…...

为机器人装“大脑” 谷歌发布RT-2大模型

大语言模型不仅能让应用变得更智能&#xff0c;还将让机器人学会举一反三。在谷歌发布RT-1大模型仅半年后&#xff0c;专用于机器人的RT-2大模型于近期面世&#xff0c;它能让机器人学习互联网上的文本和图像&#xff0c;并具备逻辑推理能力。 该模型为机器人智能带来显著升级…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...