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

dp专题13 零钱兑换II

本题链接:. - 力扣(LeetCode)

题目:

思路:

        根据题意,这是一道很裸的背包问题,其中这里是返回 背包方案数 的。

我们可以直接推出公式 : dp [ j ] += dp[ j - coins[ i ] ]

在我之前做的笔记中,写过具体的背包方案数dp公式,参考我之前的详解即可:dp专题10 目标和 

最后我们再明确一下题目,题目要求是  硬币数量是无限的,说明这是一个 完全背包问题。

完全背包问题 和 01 背包问题区别在于 遍历背包的顺序。

01   背包的  背包 遍历顺序: 逆向。

完全背包的  背包 遍历顺序: 正向。

具体原理是:

背包 逆向 遍历的时候,  物品只能 取 1 次.(01 背包)

代码详解:


for(int i = 0;i < goods.size();++i)
{for(int j = v;j >= goods[i].v;--j){dp[j] = max(dp[j],dp[j - goods.v] + goods.w);}
}/*逆向 的时候,  j == 背包容量(v)   时, 只能取当前的一个 物品 i  随后随着 --j   后面  dp[j]  紧随其后  只取一个物品 i       所以达到了,只取 一次 的效果
*/   

 背包 正向 遍历的时候,  物品可以取多次.(完全 背包)

代码详解:


for(int i = 0;i < goods.size();++i)
{for(int j = goods[i].v;j <= v;++j){dp[j] = max(dp[j],dp[j - goods.v] + goods.w);}
}/*正向 的时候,  j == 物品容量(goods.v)   时, 取当前的一个 物品 i  随后随着 ++j   后面  dp[j]  紧随其后 取一个物品 i       直到达到了 dp[v] ,使得 物品 i 取了多次
*/   

所以 完全背包问题 和 01 背包问题区别在于 遍历背包的顺序。

同样的道理,我们结合dp递推的公式 + 背包遍历顺序,就可以解出这道完全背包问题方案数的问题了。

在这里再扩展一下问题,遍历顺序中,先遍历背包还是先遍历物品?

我们再看一下这两种遍历方法的效果:

①先遍历物品再遍历背包


for(int i = 0;i < goods.size();++i)    // 遍历物品
{for(int j = goods[i].v;j <= v;++j)    // 遍历背包{dp[j] = max(dp[j],dp[j - goods.v] + goods.w);}
}/*假设 物品 等于 下标那么背包会得到的集合是:{1} {1,2} , {2}{1,2,3} , {2,3} , {3}....获取的集合中不会出现 {2,1}... 等集合说明 先遍历物品再遍历背包是一个  组合 数*/   

②先遍历背包再遍历物品

for(int j = goods[i].v;j <= v;++j)    // 遍历背包
{for(int i = 0;i < goods.size();++i)    // 遍历物品{dp[j] = max(dp[j],dp[j - goods.v] + goods.w);}
}/*假设 物品 等于 下标那么背包会得到的集合是:{1} {1,2} , {2,1} ,{2}....获取的集合中会出现 {2,1}... 等集合说明 先遍历物品再遍历背包是一个  排列 数*/   

所以 背包问题 遍历顺序中 :

先遍历物品再遍历背包: 组合 数。

先遍历背包再遍历物品: 排列 数。

综上所述。

代码详解如下:

inline int change(int& amount, vector<int>& coins) 
{vector<int>dp(amount + 1,0);dp[0] = 1;    // dp 初始化  凑成 0 有 1种方法 就是 +0// 组合数遍历for(int &i:coins)    // 遍历物品{for(int j = i;j <= amount;++j)    // 遍历背包{dp[j] += dp[j - i];    // dp 递推公式}}return dp[amount];    // 返回结果
}

最后提交:

相关文章:

dp专题13 零钱兑换II

本题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 思路&#xff1a; 根据题意&#xff0c;这是一道很裸的背包问题&#xff0c;其中这里是返回 背包方案数 的。 我们可以直接推出公式 &#xff1a; dp [ j ] dp[ j - coins[ i ] ] 在我之前…...

el-dialog嵌套使用,只显示遮罩层的问题

直接上解决方法 <!-- 错误写法 --><el-dialog><el-dialog></el-dialog></el-dialog><!-- 正确写法 --><el-dialog></el-dialog><el-dialog></el-dialog>我是不建议嵌套使用的&#xff0c;平级也能调用&#xff0c…...

响应式Web开发项目教程(HTML5+CSS3+Bootstrap)第2版 例3-5 CSS3 动画

代码 <!doctype html> <html> <head> <meta charset"utf-8"> <title>CSS3 动画</title> <style> .img {width: 150px; } keyframes rotate { 0% { transform: rotate(0deg); } 100% { transform: rotate(360deg);} } img…...

一款实用的.NET Core加密解密工具类库

前言 在我们日常开发工作中&#xff0c;为了数据安全问题对数据加密、解密是必不可少的。加密方式有很多种如常见的AES&#xff0c;RSA&#xff0c;MD5&#xff0c;SAH1&#xff0c;SAH256&#xff0c;DES等&#xff0c;这时候假如我们有一个封装的对应加密解密工具类可以直接…...

C/C++内存布局

1. C 结构体的内存布局 以一个例子来看struct的内存结构 #define NP_FUNC_WRAPPER __attribute__((optimize(0)))struct StructBody {int first_int_placeholder;int second_int_placeholder;double third_double_placeholder; };class ClassBody {public:int first_int_place…...

springboot(ssm母婴全程服务管理系统 母婴用品服务商城Java系统

springboot(ssm母婴全程服务管理系统 母婴用品服务商城Java系统 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或8.0&#xf…...

修改SSH默认端口,使SSH连接更安全

以CentOS7.9为例&#xff1a; 1、修改配置文件 vi /etc/ssh/sshd_config 2、远程电脑可连接&#xff0c;暂时将SELinux关闭 # 查询状态 getenforce # 关闭 setenforce 0 # 开启 setenforce 1 3、SELinux设置&#xff08;如果启用&#xff09;&#xff0c;semanage管理工具安…...

React16源码: React中调度之requestWork的源码实现

requestWork 1 &#xff09;概述 在 scheduleWork 中&#xff0c;找到了创建更新的fiber对应的root节点然后对它进行了一些操作之后&#xff0c;调用了 requestWork&#xff0c;开始请求工作在 requestWork 里面它会做哪些东西呢&#xff1f; 首先我们要把这个root节点加入到调…...

【白话机器学习的数学】读书笔记(3)学习分类(感知机、逻辑回归)

三、学习分类 1.分类的目的 找到一条线把白点和黑点分开。这条直线是使权重向量成为法线向量的直线。(解释见下图) 直线的表达式为&#xff1a; ω ⋅ x ∑ i 1 n ω i ⋅ x i 0 \omegax \sum_{i1}^n\omega_i x_i 0 ω⋅xi1∑n​ωi​⋅xi​0 ω \omega ω是权重向量权…...

书生·浦语大模型实战营-学习笔记3

目录 (3)基于 InternLM 和 LangChain 搭建你的知识库1. 大模型开发范式&#xff08;RAG、Fine-tune&#xff09;RAG微调 &#xff08;传统自然语言处理的方法&#xff09; 2. LangChain简介&#xff08;RAG开发框架&#xff09;3. 构建向量数据库4. 搭建知识库助手5. Web Demo部…...

MySQL下对[库]的操作

目录 创建数据库 创建一个数据库案例&#xff1a; 字符集和校验规则&#xff1a; 默认字符集&#xff1a; 默认校验规则&#xff1a; 查看数据库支持的字符集&#xff1a; 查看数据库支持的字符集校验规则&#xff1a; 校验规则对数据库的影响&#xff1a; 操作数据…...

Django(七)

1.靓号管理 1.1 表结构 根据表结构的需求&#xff0c;在models.py中创建类&#xff08;由类生成数据库中的表&#xff09;。 class PrettyNum(models.Model):""" 靓号表 """mobile models.CharField(verbose_name"手机号", max_len…...

AT24C02读写操作 一

//AT24C02初始化 void AT24C02_Init(void) { IIC_Init(); } //AT24C02的字节写入 写一个字节 void AT24C02_WordWrite(uint8_Address,uint8_t Data) { //1。主机发送开始信号 IIC_StartSignal(); //2.主机发送器件地址 写操作 IIC_SentBytes(0xA0); //3.主机等侍从机应…...

.NET 8 中引入新的 IHostedLifecycleService 接口 实现定时任务

在这篇文章中&#xff0c;我们将了解 .NET 8 中为托管服务引入的一些新生命周期事件。请注意&#xff0c;这篇文章与 .NET 8 相关&#xff0c;在撰写本文时&#xff0c;.NET 8 目前处于预览状态。在 11 月 .NET 8 最终版本发布之前&#xff0c;类型和实现可能会发生变化。要继续…...

Redis--Geo指令的语法和使用场景举例(附近的人功能)

文章目录 前言Geo介绍Geo指令使用使用场景&#xff1a;附近的人参考文献 前言 Redis除了常见的五种数据类型之外&#xff0c;其实还有一些少见的数据结构&#xff0c;如Geo&#xff0c;HyperLogLog等。虽然它们少见&#xff0c;但是作用却不容小觑。本文将介绍Geo指令的语法和…...

127.0.0.1和0.0.0.0的区别

在网络开发中&#xff0c;经常会涉及到两个特殊的IP地址&#xff1a;127.0.0.1和0.0.0.0。这两者之间有一些关键的区别&#xff0c;本文将深入介绍它们的作用和用途。 127.0.0.1 127.0.0.1 是本地回环地址&#xff0c;通常称为 “localhost”。作用是让网络应用程序能够与本地…...

SpringBoot ES 聚合后多字段加减乘除

SpringBoot ES 聚合后多字段加减乘除 在SpringData Elasticsearch中&#xff0c;聚合统计的原理主要依赖于Elasticsearch本身的聚合框架。Elasticsearch提供了强大的聚合功能&#xff0c;使得你可以对文档进行各种计算和统计&#xff0c;从而得到有关数据集的有用信息。 Elast…...

React16源码: React中requestCurrentTime和expirationTime的源码实现补充

requestCurrentTime 1 &#xff09;概述 关于 currentTime&#xff0c;在计算 expirationTime 和其他的一些地方都会用到 从它的名义上来讲&#xff0c;应等于performance.now() 或者 Date.now() 就是指定的当前时间在react整体设计当中&#xff0c;它是有一些特定的用处和一些…...

【论文阅读】Deep Graph Contrastive Representation Learning

目录 0、基本信息1、研究动机2、创新点3、方法论3.1、整体框架及算法流程3.2、Corruption函数的具体实现3.2.1、删除边&#xff08;RE&#xff09;3.2.2、特征掩盖&#xff08;MF&#xff09; 3.3、[编码器](https://blog.csdn.net/qq_44426403/article/details/135443921)的设…...

设计模式-简单工厂

设计模式-简单工厂 简单工厂模式是一个集中管理对象创建&#xff0c;并根据条件生成所需类型对象的设计模式&#xff0c;有助于提高代码的复用性和维护性&#xff0c;但可能会导致工厂类过于复杂且违反开闭原则。 抽象提取理论&#xff1a; 封装对象创建过程解耦客户端与产品…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...