518. 零钱兑换 II(力扣LeetCode)

2024-04-11 13:04

本文主要是介绍518. 零钱兑换 II(力扣LeetCode),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 518. 零钱兑换 II
    • 题目描述
    • 动态规划
      • 一维数组
        • 为什么不能交换两个for循环的顺序?
      • 二维数组

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

提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

动态规划

一维数组

这段代码是在解决一个称为"零钱兑换 II"的动态规划问题。具体来说,它计算了使用一个无限数量的不同面额硬币凑成某个总金额的所有可能组合的数目。代码使用了C++语言。下面是对这段代码的逐行解释:

// 定义一个Solution类
class Solution {
public:// 定义并实现一个名为change的公共成员函数int change(int amount, vector<int>& coins) {// dp定义了一个整型向量(dp数组),大小为amount + 1,所有值初始化为0vector<int>dp(amount+1, 0);// 将dp数组的第一项设置为1,这表示金额为0的话有1种方式(就是不用任何硬币)dp[0] = 1;// 遍历coins数组,i为索引,从0开始到coins.size() - 1for(int i = 0; i < coins.size(); i++)// 从当前硬币面额coins[i]开始,直到总金额for(int j = coins[i]; j <= amount; j++)// 更新dp[j]的值:dp[j] = dp[j] + dp[j - coins[i]]// 这表示加上用当前的硬币面额coins[i]凑出金额j的新组合数dp[j] += dp[j - coins[i]];// 最后返回dp数组的最后一项,即凑成总金额amount的组合数return dp[amount];}
};

解释一下这个动态规划的核心思想:

  • dp数组的定义:dp[i]表示凑成总金额为i的硬币组合数。
  • 初始化:由于凑成总金额为0的方式只有一种,就是不使用任何硬币,所以初始化dp[0] = 1。
  • 外层循环:遍历每一种硬币。
  • 内层循环:对于每一种硬币,更新金额从硬币面额到总金额的所有dp值。
  • 状态转移方程:dp[j] += dp[j - coins[i]]的含义是,对于每个金额j,考虑当前的硬币面额coins[i],如果我们知道了组成金额j - coins[i]的组合数(即dp[j - coins[i]]),那么就可以通过添加一个coins[i]硬币来得到金额j的一个新的组合。所以,我们要将组成金额j - coins[i]的所有组合数加到dp[j]上。

这个算法的时间复杂度是O(n*m),n是金额amount,m是硬币种类数。空间复杂度是O(n),因为我们使用了一个n + 1大小的dp数组。

为什么不能交换两个for循环的顺序?

在这个特定的动态规划问题中,两个for循环的顺序决定了硬币组合数是如何被计算的,特别是它们影响了状态转移方程的更新方式。如果交换了循环的顺序,将会改变动态规划算法的整个逻辑。

原始顺序(先遍历硬币,然后遍历金额)的循环确保了以下几点:

  1. 组合性:当计算dp[j]时(即凑成金额j的方法数),算法仅考虑使用当前硬币和之前考虑过的硬币的组合。这意味着,对于每个硬币,你都是在累积之前的结果上增加新的可能性。

  2. 无重复:这个顺序确保了在计算组合数时,相同面额的硬币不会被重复计算。即我们不会得到多个考虑顺序不同但实际上相同的硬币组合。

  3. 有序:由于每次循环都是在之前硬币的基础上加上新硬币,因此所有的组合都是以一种有序的方式生成的。

如果交换了for循环的顺序,算法将会改变上述逻辑,导致以下问题:

  • 每次计算dp[j]时,都会考虑所有硬币,这意味着同一金额会被重复计算多次,从而破坏了动态规划的基本原则。
  • 容易出现重复组合,因为对于每个金额,你都在尝试所有的硬币,无法保证硬币使用的唯一顺序,从而可能导致重复的组合方式被计数。
  • 缺乏顺序性,因为你在每个金额的计算中都包含了所有的硬币,这样就会有多种硬币组合顺序产生相同的金额,这些都被错误地算作不同的组合。

因此,保持原始的循环顺序对于解决这个动态规划问题是很重要的,它确保了算法的正确性和效率。

二维数组

这段代码是解决"零钱兑换 II"问题的动态规划解法。下面是对代码的详细注释:

class Solution {
public:int change(int amount, vector<int>& coins) {// 初始化动态规划表格。行数为coins.size()+1,代表0到coins.size个硬币,列数为amount+1,代表0到amount的金额。// dp[i][j]表示使用前i种硬币凑成金额j的方法数。vector<vector<int>> dp(coins.size()+1,vector<int>(amount+1,0));// base case:当金额为0时,即j=0,不使用任何硬币就能凑齐,因此方法数为1。dp[0][0]=1;// 遍历所有的硬币种类for(int i=1;i<=coins.size();i++){// 对于每一种硬币,遍历所有可能的金额for(int j=0;j<=amount;j++){// dp[i][j]首先继承dp[i-1][j]的值,即不使用第i种硬币时凑成金额j的方法数。dp[i][j]=dp[i-1][j];// 如果当前金额j大于等于当前考虑的硬币面额coins[i-1],// 则可以考虑使用这种硬币。此时的方法数为dp[i][j-coins[i-1]],// 加上这种硬币之前的方法数,因为dp[i][j-coins[i-1]]已经计算了使用前i种硬币凑成金额j-coins[i-1]的方法数。if(j>=coins[i-1])dp[i][j]+=dp[i][j-coins[i-1]];}}// 返回使用所有硬币凑成总金额amount的方法数。return dp[coins.size()][amount];}
};

核心思想:

  • 动态规划表dp的大小为(coins.size()+1) * (amount+1)dp[i][j]表示使用前i种硬币(其中硬币种类从0开始编号)凑成金额j的方法数。
  • 初始化dp[0][0]=1表示不使用任何硬币凑成金额0的方法有1种。
  • 外层循环遍历硬币种类,内层循环遍历可能的金额。
  • 对于每一种硬币coins[i-1]和每一个金额j,如果j大于等于当前硬币的面额,我们有两个选择:不使用当前的硬币(继承dp[i-1][j]的值),或者使用当前的硬币(dp[i][j-coins[i-1]]加上当前硬币的数量)。
  • 最终,dp[coins.size()][amount]是使用所有硬币凑成金额amount的方法数。

这篇关于518. 零钱兑换 II(力扣LeetCode)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/894154

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图