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
本题链接:. - 力扣(LeetCode) 题目: 思路: 根据题意,这是一道很裸的背包问题,其中这里是返回 背包方案数 的。 我们可以直接推出公式 : dp [ j ] dp[ j - coins[ i ] ] 在我之前…...

el-dialog嵌套使用,只显示遮罩层的问题
直接上解决方法 <!-- 错误写法 --><el-dialog><el-dialog></el-dialog></el-dialog><!-- 正确写法 --><el-dialog></el-dialog><el-dialog></el-dialog>我是不建议嵌套使用的,平级也能调用,…...
响应式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加密解密工具类库
前言 在我们日常开发工作中,为了数据安全问题对数据加密、解密是必不可少的。加密方式有很多种如常见的AES,RSA,MD5,SAH1,SAH256,DES等,这时候假如我们有一个封装的对应加密解密工具类可以直接…...
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系统 开发语言:Java 框架:ssm/springboot vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:mysql 5.7(或8.0…...

修改SSH默认端口,使SSH连接更安全
以CentOS7.9为例: 1、修改配置文件 vi /etc/ssh/sshd_config 2、远程电脑可连接,暂时将SELinux关闭 # 查询状态 getenforce # 关闭 setenforce 0 # 开启 setenforce 1 3、SELinux设置(如果启用),semanage管理工具安…...
React16源码: React中调度之requestWork的源码实现
requestWork 1 )概述 在 scheduleWork 中,找到了创建更新的fiber对应的root节点然后对它进行了一些操作之后,调用了 requestWork,开始请求工作在 requestWork 里面它会做哪些东西呢? 首先我们要把这个root节点加入到调…...

【白话机器学习的数学】读书笔记(3)学习分类(感知机、逻辑回归)
三、学习分类 1.分类的目的 找到一条线把白点和黑点分开。这条直线是使权重向量成为法线向量的直线。(解释见下图) 直线的表达式为: ω ⋅ x ∑ i 1 n ω i ⋅ x i 0 \omegax \sum_{i1}^n\omega_i x_i 0 ω⋅xi1∑nωi⋅xi0 ω \omega ω是权重向量权…...

书生·浦语大模型实战营-学习笔记3
目录 (3)基于 InternLM 和 LangChain 搭建你的知识库1. 大模型开发范式(RAG、Fine-tune)RAG微调 (传统自然语言处理的方法) 2. LangChain简介(RAG开发框架)3. 构建向量数据库4. 搭建知识库助手5. Web Demo部…...

MySQL下对[库]的操作
目录 创建数据库 创建一个数据库案例: 字符集和校验规则: 默认字符集: 默认校验规则: 查看数据库支持的字符集: 查看数据库支持的字符集校验规则: 校验规则对数据库的影响: 操作数据…...

Django(七)
1.靓号管理 1.1 表结构 根据表结构的需求,在models.py中创建类(由类生成数据库中的表)。 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 接口 实现定时任务
在这篇文章中,我们将了解 .NET 8 中为托管服务引入的一些新生命周期事件。请注意,这篇文章与 .NET 8 相关,在撰写本文时,.NET 8 目前处于预览状态。在 11 月 .NET 8 最终版本发布之前,类型和实现可能会发生变化。要继续…...

Redis--Geo指令的语法和使用场景举例(附近的人功能)
文章目录 前言Geo介绍Geo指令使用使用场景:附近的人参考文献 前言 Redis除了常见的五种数据类型之外,其实还有一些少见的数据结构,如Geo,HyperLogLog等。虽然它们少见,但是作用却不容小觑。本文将介绍Geo指令的语法和…...
127.0.0.1和0.0.0.0的区别
在网络开发中,经常会涉及到两个特殊的IP地址:127.0.0.1和0.0.0.0。这两者之间有一些关键的区别,本文将深入介绍它们的作用和用途。 127.0.0.1 127.0.0.1 是本地回环地址,通常称为 “localhost”。作用是让网络应用程序能够与本地…...
SpringBoot ES 聚合后多字段加减乘除
SpringBoot ES 聚合后多字段加减乘除 在SpringData Elasticsearch中,聚合统计的原理主要依赖于Elasticsearch本身的聚合框架。Elasticsearch提供了强大的聚合功能,使得你可以对文档进行各种计算和统计,从而得到有关数据集的有用信息。 Elast…...
React16源码: React中requestCurrentTime和expirationTime的源码实现补充
requestCurrentTime 1 )概述 关于 currentTime,在计算 expirationTime 和其他的一些地方都会用到 从它的名义上来讲,应等于performance.now() 或者 Date.now() 就是指定的当前时间在react整体设计当中,它是有一些特定的用处和一些…...

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

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

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出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装: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 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

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的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

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