当前位置: 首页 > 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; 封装对象创建过程解耦客户端与产品…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...