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

代码随想录算法训练营第46天 | 完全背包,139.单词拆分

动态规划章节理论基础:

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

完全背包理论基础:

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

139.单词拆分

题目链接:https://leetcode.cn/problems/word-break/

思路:

单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词,说明就是一个完全背包!

动规五部曲:
(1)确定dp数组以及下标含义
dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

(2)确定递归公式
如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

(3)dp数组初始化
从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

那么dp[0]有没有意义呢?

dp[0]表示如果字符串为空的话,说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。

(4)确定遍历顺序
而本题其实我们求的是排列数,为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。

所以说,本题一定是 先遍历 背包,再遍历物品。

(5)举例推导dp数组
以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例,dp状态如图:
在这里插入图片描述
dp[s.size()]就是最终结果。

代码:

class Solution {public int change(int amount, int[] coins) {int len = coins.length;int[]dp = new int[amount+1];dp[0] = 1;for(int i=0; i< len;i++){for(int j=coins[i];j<= amount;j++){// dp[j] = Math.max(dp[j],dp[j-coins[i]]+1);// 装满背包有几种方法,公式都是:dp[j] += dp[j - nums[i]];// 和494.目标和这道题的递推公式是一样的dp[j] = dp[j] + dp[j-coins[i]];}}return dp[amount];}
}

相关文章:

代码随想录算法训练营第46天 | 完全背包,139.单词拆分

动态规划章节理论基础&#xff1a; https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 完全背包理论基础&#xff1a; https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9…...

rust - 将windows剪贴板的截图保存为png

本文提供了将windows系统的截图另存为png格式图片的方法。 添加依赖 cargo add clipboard-win cargo add image cargo add windows配置修改windows依赖特性 [dependencies] image "0.25.0"[target.cfg(windows).dependencies] windows "0.51.1" clipb…...

pyflink1.18.0 报错 TypeError: cannot pickle ‘_thread.lock‘ object

完整报错 Traceback (most recent call last):File "/Users//1.py", line 851, in <module>ds1 = my_datastream.key_by(lambda x: x[0]).process(MyProcessFunction()) # 返回元组即: f0 f1 f2 三列File "/Users/thomas990p/bigdataSoft/minicondaarm/…...

算法学习系列(四十一):Flood Fill算法

目录 引言一、池塘计数二、城堡问题三、山峰和山谷 引言 关于这个 F l o o d F i l l Flood\ Fill Flood Fill 算法&#xff0c;其实我觉得就是一个 B F S BFS BFS 算法&#xff0c;模板其实都是非常相似的&#xff0c;只不过有些变形而已&#xff0c;然后又叫这个名字。关于…...

Re62:读论文 GPT-2 Language Models are Unsupervised Multitask Learners

诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文全名&#xff1a;Language Models are Unsupervised Multitask Learners 论文下载地址&#xff1a;https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learner…...

stm32-编码器测速

一、编码器简介 编码电机 旋转编码器 A,B相分别接通道一和二的引脚&#xff0c;VCC&#xff0c;GND接单片机VCC&#xff0c;GND 二、正交编码器工作原理 以前的代码是通过触发外部中断&#xff0c;然后在中断函数里手动进行计次。使用编码器接口的好处就是节约软件资源。对于频…...

全国各省市县统计年鉴/中国环境统计年鉴/中国工业企业数据库/中国专利数据库/污染排放数据库

统计年鉴是指以统计图表和分析说明为主&#xff0c;通过高度密集的统计数据来全面、系统、连续地记录年度经济、社会等各方面发展情况的大型工具书来获取统计数据资料。 统计年鉴是进行各项经济、社会研究的必要前提。而借助于统计年鉴&#xff0c;则是研究者常用的途径。目前国…...

【LAMMPS学习】二、LAMMPS安装(2)MacOS和Win安装

2. LAMMPS安装 您可以将LAMMPS下载为可执行文件或源代码。 在下载LAMMPS源代码时&#xff0c;还必须构建LAMMPS。但是对于在构建中包含或排除哪些特性&#xff0c;您有更大的灵活性。当您下载并安装预编译的LAMMPS可执行文件时&#xff0c;您只能安装可用的LAMMPS版本以及这些…...

如何解决网络中IP地址发生冲突故障?

0、前言 本专栏为个人备考软考嵌入式系统设计师的复习笔记&#xff0c;未经本人许可&#xff0c;请勿转载&#xff0c;如发现本笔记内容的错误还望各位不吝赐教&#xff08;笔记内容可能有误怕产生错误引导&#xff09;。 1、个人IP地址冲突解决方案 首先winR&#xff0c;调出…...

机器学习常用框架

机器学习是人工智能的一个重要分支&#xff0c;它通过让计算机系统利用数据自我学习来改进任务执行的能力。在机器学习领域&#xff0c;有许多成熟的框架被广泛使用&#xff0c;这些框架提供了构建和训练机器学习模型的工具。以下是一些常用的机器学习框架&#xff1a; Tensor…...

计算机网络——物理层(信道复用技术)

计算机网络——物理层&#xff08;信道复用技术&#xff09; 信道复用技术频分多址与时分多址 频分复用 FDM (Frequency Division Multiplexing)时分复用 TDM (Time Division Multiplexing)统计时分复用 STDM (Statistic TDM)波分复用码分复用 我们今天接着来看信道复用技术&am…...

【Qt问题】使用QSlider创建滑块小部件无法显示

问题描述&#xff1a; 使用QSlider创建滑块小部件用于音量按钮的时候&#xff0c;无法显示&#xff0c;很奇怪&#xff0c;怎么都不显示 一直是这个效果&#xff0c;运行都没问题&#xff0c;但是就是不出现。 一直解决不了&#xff0c;最后我在无意中&#xff0c;在主程序中…...

Linux--Shell脚本安装 httpd 和 修改IP

shell脚本 关闭防火墙、安装httpd、启动httpd [rootnode11 ~]# mkdir shell[rootnode11 ~]# vim abc.sh #!/bin/bash#安装httpd服务#1、挂载 准备yum源 mount /dev/sr0 /mnt &> /dev/nulldf$(df -h | grep /dev/sr0 | awk {print $6})if [ "$df" "/mn…...

mysql 常见问题

1、count(*) 、 count(1) 和 count&#xff08;字段&#xff09;区别 在MySQL中&#xff0c;COUNT(*)、COUNT(1) 和 COUNT(字段) 是用于统计行数的函数&#xff0c;它们的主要区别在于&#xff1a; COUNT(*)&#xff1a;会统计符合条件的所有行的数量&#xff0c;不管这些行中…...

考研机试题

目录 头文件与STL动态规划最大数组子串和最长公共子序列最长连续公共子串最长递增子序列最大上升子序列和0-1背包多重背包多重背包问题 I整数拆分最小邮票最大子矩阵 数学问题朴素法筛素数线性筛素数快速幂 石子合并锯木棍并查集Dijkstra单源最短路Python进制转换(整数无限大)全…...

Java基础知识总结(6)

String类中常用的类方法&#xff1a; 方法名称描述format(String format, Object... args)使用指定的格式字符串和参数返回一个格式化字符串。 format - 格式字符串 args - 格式字符串中由格式说明符引用的参数。如果还有格式说明符以外的参数&#xff0c;则忽略这些额外的参数…...

JAVA基础—关于Java的反射机制

1. Java的反射机制是什么&#xff1f; 反射(reflection) 当我们谈及反射&#xff0c;可以将其比作正在照镜子的行为。就像你可以在禁止中看到自己的反射一样&#xff0c;程序在运行时可以检查自身的机构和行为。这意味这程序可以动态地了解自己地组成部分&#xff0c;比如类、…...

Hive中的explode函数、posexplode函数与later view函数

1.概述 在离线数仓处理通过HQL业务数据时&#xff0c;经常会遇到行转列或者列转行之类的操作&#xff0c;就像concat_ws之类的函数被广泛使用&#xff0c;今天这个也是经常要使用的拓展方法。 2.explode函数 2.1 函数语法 -- explode(a) - separates the elements of array …...

北京市委统战部领导一行莅临百望云视察调研

“当今时代&#xff0c;数字技术、数字经济是世界科技革命和产业变革的先机&#xff0c;是新一轮国际竞争重点领域”。 为了解数字标杆企业的发展现状&#xff0c;促进新质生产力与实体产业的协同与赋能&#xff0c;近日&#xff0c;北京市委统战部非公经济处处长王雷、副处长徐…...

使用Python进行数据库连接与操作SQLite和MySQL【第144篇—SQLite和MySQL】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 使用Python进行数据库连接与操作&#xff1a;SQLite和MySQL 在现代应用程序开发中&#xf…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...