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

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

如何为服务器生成TLS证书

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

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...