leetcode hot100零钱兑换Ⅱ

在这里插入图片描述
本题可以看出也是背包问题,但区别于之前的01背包问题,这个是完全背包问题的变形形式。

下面介绍01背包和完全背包的区别与联系:

  1. 01背包是背包中的物品只能用一次,不可以重复使用,而完全背包则是可以重复使用。
  2. 01/完全背包的递推公式(这里都是以一维数组的情况举例)是dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i])。
  3. 01背包的遍历顺序是先物品,再背包,并且背包遍历的时候是需要倒序遍历的,而完全背包则不需要,直接先物品再背包(背包需要正序),其实先背包再物品也可以,但为了方便记忆则和01保持一致。

而当在完全背包的变形形式,比如本题是要求组合数,组合是没有顺序的,只需要找出对应的元素就可以,所以递推公式是dp[j] += dp[j-nums[i]]。

所以本题中,我们可以想将背包中的硬币个数,不限制次数的选取,最后求凑成金额为amount的种类一共有多少种。

所以采用动态规划完全背包求组合情况

dp[j]表示背包容量为j的价值为dp[j]。
dp[j] += dp[j-nums[i]]
dp[0] = 1 (注意,这里必须是1,如果不是1的话没办法推出后面的数据,后面数据就都变成0了)。
遍历顺序应该先物品再背包,并且背包内层循环应该由小到大遍历。
打印

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

注意:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/398836.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

体验一下UE5.3的Skeletal Editor

UE5.3中增加了蒙皮网格骨架编辑工具&#xff0c;用户无需导出Fbx就可以直接编辑蒙皮网格&#xff0c;支持修改绑定姿势的骨骼位置、修改蒙皮权重、对已蒙皮多边形进行编辑以及对蒙皮网格减免等操作&#xff0c;就来体验一下。 1.加载插件 要使用Skeletal Editor功能&#xff…

使用系统调用实现shell命令之【ls -l】

时间获取: 1.time time_t time(time_t *tloc); 功能: 返回1970-1-1到现在的秒数&#xff08;格林威治时间&#xff09; 参数: tloc:存放秒数空间首地址 返回值: 成功返回秒数 失败返回-1 2.localtime stru…

Stable Diffusion——基础模型、VAE、LORA、Embedding各个模型的介绍与使用方法

前言 Stable Diffusion&#xff08;稳定扩散&#xff09;是一种生成模型&#xff0c;基于扩散过程来生成高质量的图像。它通过一个渐进过程&#xff0c;从一个简单的噪声开始&#xff0c;逐步转变成目标图像&#xff0c;生成高保真度的图像。这个模型的基础版本是基于扩散过程…

ESMFold conda安装、使用及与AlphaFold的简单比较

文章目录 前言一、ESMFold是什么&#xff1f;二、安装步骤1. 确认安装环境&#xff1a;cuda toolkit版本2. 创建ESMFold conda环境并安装Step 1&#xff1a;创建conda环境&#xff0c;下载需要的包Step 2&#xff1a;激活conda环境&#xff0c;继续pip安装 3. 运行结构预测 三、…

pom.xml常见依赖及其作用

1.org.mybatis.spring.boot下的mybatis-spring-boot-starter&#xff1a;这个依赖是mybatis和springboot的集成库&#xff0c;简化了springboot项目中使用mybatis进行持久化操作的配置和管理 2.org.projectlombok下的lombok&#xff1a;常用注解Data、NoArgsConstructor、AllA…

【Vuforia+Unity】AR02-长方体物体识别

1.创建模型 选择多维长方体图&#xff0c;这个长方体是生活中的真实物体的拍摄图&#xff0c;提前把6个面拍摄好并裁剪干净。 官网创建模型https://developer.vuforia.com/targetmanager/project/targets?projectId0ddbb5c17e7f4bf090834650bbea4995&avfalse 设置长宽高…

Rabbitmq入门与应用(六)-rabbitmq的消息确认机制

rabbitmq的消息确认机制 确认消息是否发送给交换机 配置 server:port: 11111 spring:rabbitmq:port: 5672host: 192.168.201.81username: adminpassword: 123publisher-confirm-type: correlated编码RabbitTemplate.ConfirmCallback ConfirmCallback 是一个回调接口&#xf…

突出最强算法模型——回归算法 !!

文章目录 1、特征工程的重要性 2、缺失值和异常值的处理 &#xff08;1&#xff09;处理缺失值 &#xff08;2&#xff09;处理异常值 3、回归模型的诊断 &#xff08;1&#xff09;残差分析 &#xff08;2&#xff09;检查回归假设 &#xff08;3&#xff09;Cooks 距离 4、学…

汽车电子论文学习---电动汽车用高功率密度碳化硅电机控制器研究

关键重点&#xff1a; sic的特点&#xff1a;耐压高、开关速度快、开关损耗小&#xff1b;采用sic的控制器&#xff0c;损耗降低70%&#xff0c;续航里程提高5%。sic的模块并联设计难度高于IGBT模块&#xff1b;多芯片并联导致热耦合问题、温升不均&#xff0c;导致部分芯片率…

合纵连横 – 以 Flink 和 Amazon MSK 构建 Amazon DocumentDB 之间的实时数据同步

在大数据时代&#xff0c;实时数据同步已经有很多地方应用&#xff0c;包括从在线数据库构建实时数据仓库&#xff0c;跨区域数据复制。行业落地场景众多&#xff0c;例如&#xff0c;电商 GMV 数据实时统计&#xff0c;用户行为分析&#xff0c;广告投放效果实时追踪&#xff…

【git】提交信息写错了,使用 amend 或者 reset 修改最近一次的提交信息 ,修改上上次/以前的提交信息

如果你的提交信息写错了&#xff0c;比如下面&#xff0c;你想修改【初始化项目】这5个字 修改最近一次的提交新的两个办法 &#xff08;1&#xff09;使用 reset 把这个提交重置&#xff0c;然后重新提交&#xff0c;reset 的使用方法请参考这篇文章。但是 reset 这种方法只能…

计算机设计大赛 深度学习人体跌倒检测 -yolo 机器视觉 opencv python

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的人体跌倒检测算法研究与实现 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满…

消息队列-RabbitMQ:发布确认—发布确认逻辑和发布确认的策略

九、发布确认 1、发布确认逻辑 生产者将信道设置成 confirm 模式&#xff0c;一旦信道进入 confirm 模式&#xff0c;所有在该信道上面发布的消息都将会被指派一个唯一的 ID (从 1 开始)&#xff0c;一旦消息被投递到所有匹配的队列之后&#xff0c;broker 就会发送一个确认给…

设计模式二:代理模式

1、什么是动态代理 可能很多小伙伴首次接触动态代理这个名词的时候&#xff0c;或者是在面试过程中被问到动态代理的时候&#xff0c;不能很好的描述出来&#xff0c;动态代理到底是个什么高大上的技术。不方&#xff0c;其实动态代理的使用非常广泛&#xff0c;例如我们平常使…

华为配置直连三层组网直接转发示例

华为配置直连三层组网直接转发示例 组网图形 图1 配置直连三层组网直接转发示例组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件扩展阅读 业务需求 企业用户接入WLAN网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff…

无人机的视频图传技术有哪些?

在操控无人机时&#xff0c;视频图传技术显得尤为关键。通过这项技术&#xff0c;无人机的摄像头所捕捉的画面能实时回传至遥控器&#xff0c;使操作者全面掌握无人机的拍摄情况。同时&#xff0c;无人机图传技术也是衡量无人机性能的重要标准&#xff0c;它关乎飞行距离与时间…

SG-8201CJA(汽车可编程晶体振荡器)

爱普生的SG-8021CJA是一款符合AEC-Q100标准的晶体振荡器&#xff0c;专为要求苛刻的汽车/ADAS应用&#xff08;如激光雷达和相机ECU&#xff09;而设计。它采用爱普生的内部低噪声小数NPLL&#xff0c;输出 频率高达170MHz&#xff0c;相位抖动小于1/25&#xff0c;稳定性比之前…

基于多种机器学习模型的西北地区蒸散发模拟与趋势分析_季鹏_2023

基于多种机器学习模型的西北地区蒸散发模拟与趋势分析_季鹏_2023 摘要关键词 1 资料和方法1. 1 研究区域与观测数据1. 2 机器学习模型构建与验证方法1. 3 SHAP 可解释性方法 2 主要结果2. 1 不同模型的模拟性能和泛化能力2. 2 不同模型的可解释性分析2. 3 5 km 分辨率格点蒸散发…

Qt _day1

1.思维导图 2.设计一个简单登录界面 #include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {this->setWindowTitle("原神启动"); // this->setStyleSheet("background-color:rgb(255,184,64)");this->setStyl…

游戏行业洞察:分布式开源爬虫项目在数据采集与分析中的应用案例介绍

前言 我在领导一个为游戏行业巨头提供数据采集服务的项目中&#xff0c;我们面临着实时数据需求和大规模数据处理的挑战。我们构建了一个基于开源分布式爬虫技术的自动化平台&#xff0c;实现了高效、准确的数据采集。通过自然语言处理技术&#xff0c;我们确保了数据的质量和…