LeetCode 518.零钱兑换II 动态规划 + 完全背包 + 组合数

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:amount = 10, coins = [10] 
输出:1

>>思路和分析

  • ① 钱币数量不限,可以知道这是一个完全背包的问题;
  • ② 与纯完全背包式凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数!

注意题目描述中是凑成总金额的硬币组合数,为什么强调是组合数呢?

例如示例一:

        5 = 2 + 2 + 1 

        5 = 2 + 1 + 2

这是一种组合,都是 2 2 1。如果问的是排列数,上面就是两种排列了。

注意:组合不强调元素之间的顺序,排列强调元素之间的顺序

>>动规五部曲

1.确定dp数组以及下标的含义

        dp[j] : 凑成总金额 j 的货币组合数 为 dp[j]

2.确定递推公式

  •  dp[j] 就是所有的 dp[j - coins[i]] (考虑 coins[i] 的情况)相加
  •  所以递推公式:dp[j] += dp[j - coins[i]];

0-1背包题目有这篇LeetCode 494.目标和中讲解了,求装满背包有几种方法,公式都是:

                                                        dp[j] += dp[j - nums[i]];

3.dp数组初始化

dp[0] = 1,这是递归公式的基础;若dp[0] = 0的话,后面所有推导出来的值都是0了

下标非0的dp[j]初始化为0,这样累计加dp[j - coins[i]]的时候才不会影响真正的 dp[j]

dp[0] = 1 还说明了一种情况:如果正好选了coins[i]后,也就是 j - coins[i] == 0的情况表示这个硬币刚好能选,此时 dp[0] 为1 表示只选coins[i]存在这样的一种选法

4.确定遍历顺序

  • 方式一:先遍历物品再遍历背包
  • 方式二:先遍历背包再遍历物品

在纯完全背包中,先遍历物品再遍历背包,还是先遍历背包再遍历物品,两者都可以!

本题就不行了!因为纯完全背包求得装满背包的最大价值是多少,和凑成总和的元素有没有顺序是没有关系的,即:有顺序也行,没顺序也行!

但在本题中要求凑合总和的组合数,元素之间明确要求没有顺序的。所以只能是方式一这种遍历顺序,那为什么不能是方式二呢?

对于方式一在完全背包中:外层for 循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}

假设:coins[0] = 1,coins[1] = 5

那么就是先把1加入计算,再把5加入计算,得到的只有{1,5}这种情况,是不会出现{5,1}这种情况的,所以这种遍历顺序中dp[j]里计算的是组合数!

对于方式二在完全背包中:外层for遍历背包(金钱总额),内层for 循环遍历物品(钱币)的情况

for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}

背包容量的每一个值,都是经过1 和 5的计算,包含了 {1,5} 和 {5,1}两种情况。此时dp[j]里算出来的就是排列数!

5.举例推导dp数组

输入:amount = 5,coins = [1,2,5],dp状态图如下:

dp[amout]为最终结果

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包dp[j] += dp[j - coins[i]];}}return dp[amount];}
};
  • 时间复杂度:O(mn),其中 m 是 amount,n是coins的长度
  • 空间复杂度:O(m)

【总结】

本题的递推公式,在 494.目标和 中已经做了详细讲解,而本题的难点主要在于遍历顺序!

  • 在求装满背包有几种方案的时候,确定遍历顺序是非常关键的;
  • 如果求组合数,那就是外层for循环遍历物品,内层for循环遍历背包
  • 如果求排列数,那就是外层for循环遍历背包,内层for循环遍历物品

来自代码随想录的课堂截图:

参考文章和视频:

代码随想录 (programmercarl.com)

动态规划之完全背包,装满背包有多少种方法?组合与排列有讲究!| LeetCode:518.零钱兑换II_哔哩哔哩_bilibili

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

leetCode 62.不同路径 动态规划 + 空间复杂度优化

62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xf…

大数据之Flume

Flume概述 一个高可用&#xff08;稳定&#xff09;&#xff0c;高可靠&#xff08;稳定&#xff09;&#xff0c;分布式的海量日志采集&#xff0c;聚合和传输的系统。Flume基于流式架构&#xff0c;灵活简单。日志文件即txt文件&#xff0c;不能传输音频&#xff0c;视频&am…

194、SpringBoot -- 下载和安装 Erlang 、 RabbitMQ

本节要点&#xff1a; 一些命令&#xff1a; 小黑窗输入&#xff1a; rabbitmq-plugins enable rabbitmq_management 启动控制台插件 rabbitmq-server 启动rabbitMQ服务器 管理员启动小黑窗&#xff1a; rabbitmq-service install 添加rabbitMQ为本地服务 启动浏览器访问 ht…

stl格式-3D三角形

文章目录 什么是stl文件?格式首选stl的语法1.这是一个stl格式的文件:(ASCII码)2.下面先举个例子(难度略微提示)补充:关于\<\<我试了一下:这个法线你随便写好像也没问题\>> 3.来个立方体4.最后再写一个由三个直角形组成的立方体(直棱锥)5.amend 修正(右手定则,法线…

如何定时备份使用Docker构建的MySQL容器中的数据库

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

单目标应用:基于螳螂搜索算法(Mantis Search Algorithm,MSA)的微电网优化调度MATLAB

一、螳螂搜索算法 螳螂搜索算法&#xff08;Mantis Search Algorithm&#xff0c;MSA&#xff09;由Mohamed Abdel-Basset等人于2023年提出&#xff0c;该算法模拟螳螂独特的狩猎和性同类相食行为。MSA由三个优化阶段组成&#xff0c;包括寻找猎物&#xff08;探索&#xff09…

OpenHarmony自定义组件介绍

一、创建自定义组件 在ArkUI中&#xff0c;UI显示的内容均为组件&#xff0c;由框架直接提供的称为系统组件&#xff0c;由开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑…

Windows 下安装和配置 Redis (详细图文)

目录 下载 Redis安装 Redis配置 Redis修改密码(可选)配置环境变量注册系统服务 Redis 桌面管理工具附&#xff1a;开源项目微服务商城项目前后端分离项目 下载 Redis 访问 Redis 下载地址&#xff1a;https://github.com/tporadowski/redis/releases 下载 Redis 时&#xff0c…

Golang的测试、基准测试和持续集成

在Golang中&#xff0c;内置的垃圾回收器处理内存管理&#xff0c;自动执行内存分配和释放。 单元测试是软件开发中至关重要的一个方面&#xff0c;它确保了代码的正确性并在开发过程中尽早发现错误。在Go中&#xff0c;编写有效的单元测试非常简单&#xff0c;并为开发人员提…

Bee2.1.8支持Spring Boot 3.0.11,active命令行选择多环境,多表查改增删(bee-spring-boot发布,更新maven)

天下大势&#xff0c;分久必合&#xff01; Hibernate/MyBatis plus Sharding JDBC Jpa Spring data GraphQL App ORM (Android, 鸿蒙) Bee Spring Cloud 微服务使用数据库更方便&#xff1a;Bee Spring Boot; 轻松支持多数据源&#xff0c;Sharding, Mongodb. 要整合一堆的…

【Java 进阶篇】深入理解 SQL 聚合函数

在 SQL 数据库中&#xff0c;聚合函数是一组强大的工具&#xff0c;用于处理和分析数据。它们可以帮助您对数据进行统计、计算总和、平均值、最大值、最小值等操作。无论您是数据库开发者、数据分析师还是希望更好地了解 SQL 数据库的用户&#xff0c;了解聚合函数都是非常重要…

【算法练习Day8】 kmp算法找出字符串中第一个匹配项的下标反转字符串中的单词重复的子字符串

、​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 kmp算法找出字符串中第…

ubuntu18.04 OpenGL开发(显示YUV)

源码参考&#xff1a;https://download.csdn.net/download/weixin_55163060/88382816 安装opengl库 sudo apt install libglu1-mesa-dev freeglut3-dev mesa-common-dev 安装opengl工具包 sudo apt install mesa-utils 检查opengl版本信息&#xff08;桌面终端执行&#xff09…

UWB技术在汽车智能制造的应用

返修区车辆管理项目 应用背景 在车辆总装生产线中&#xff0c;车辆下线后检测与返修是最后一个关键环节&#xff0c;整车一旦下线&#xff0c;由于流水线装配工艺、来料等原因&#xff0c;可能会出现部分整车存在瑕疵&#xff0c;进而进入返修区域待检。由于可能出现问题的不确…

【EI会议征稿】第三届机械、建模与材料工程国际学术会议(I3ME 2023)

第三届机械、建模与材料工程国际学术会议&#xff08;I3ME 2023&#xff09; 2023 3rd International Conference on Mechanical, Modeling and Materials Engineering 第三届机械、建模与材料工程国际学术会议&#xff08;I3ME 2023&#xff09;将于2023年12月1-3日在中国长春…

五子棋AI算法和开局定式(直指13式)破解

五子棋AI算法和开局定式&#xff08; 直指13式 &#xff09;破解 先前发了几篇五子棋游戏程序设计的博文&#xff0c;设计了游戏程序&#xff0c;也设计了AI智能奕棋的算法&#xff0c;运行程序检测算法的可行性&#xff0c;完成人机模式游戏功能的设置。这还不够&#xff0c;…

十六.镜头知识之工业镜头的质量判断因素

十六.镜头知识之工业镜头的质量判断因素 文章目录 十六.镜头知识之工业镜头的质量判断因素1.分辨率(Resolution)2.明锐度(Acutance)3.景深(DOF)&#xff1a;4. 最大相对孔径与光圈系数5.工业镜头各参数间的相互影响关系5.1.焦距大小的影响情况5.2.光圈大小的影响情况5.3.像场中…

WebPack5进阶使用总结(二)

WebPack5进阶使用总结 1、处理js资源1.1、Eslint1.2、在webpack中使用Eslint1.3、Babel1.4、在webpack中使用 2、处理HTML资源3、开发服务器&自动化4、生产模式介绍5、Css处理5.1、Css兼容性处理5.2、合并配置5.3、Css压缩 配套视频&#xff1a;尚硅谷Webpack5入门到原理 配…

STM32H7系列MPU与CACHE以及RAM

一、启用cache 启用cache很简单&#xff0c;就是这两句&#xff0c;分别打开I-Cache和D-Cache&#xff0c;但是如果只使用这两句&#xff0c;再操作DMA和FLASH时就很有可能遇到问题&#xff0c;后面会具体说明。 SCB_EnableICache();//使能I-CacheSCB_EnableDCache();//使能D-…

Android studio “Layout Inspector“工具在Android14 userdebug设备无法正常使用

背景描述 做rom开发的都知道&#xff0c;“Layout Inspector”和“Attach Debugger to Android Process”是studio里很好用的工具&#xff0c;可以用来查看布局、调试系统进程&#xff08;比如setting、launcher、systemui&#xff09;。 问题描述 最进刚开始一个Android 14…