零钱兑换Ⅱ(LeetCode-518)

简介: 零钱兑换Ⅱ(LeetCode-518)

2. 零钱兑换Ⅱ(LeetCode-518)


题目

给你一个整数数组 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


思路

本题要点:


硬币有无限个,所以完全背包问题

本题要求凑成总金额的个数

五部曲


dp[j] 含义


凑成总金额为 j jj 的硬币组合数(背包的容量为 j jj 的背包恰好装满的方法数)

递推公式


d p [ j ] = d p [ j ] + d p [ j − c o i n s [ i ] ]

数组初始化


dp[0]=1 从数组含义看:凑成总金额为零的硬币组合数为一

遍历顺序


先遍历物品,嵌套遍历背包,且背包遍历要正序

本题不是纯完全背包问题,不能交换顺序。因为本题求的是组合数,要求元素之间没有顺序。

测试用例



代码展示

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {
        vector<int> dp(amount + 1);
        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];
    }
};
目录
相关文章
|
4月前
|
Python
【Leetcode刷题Python】518. 零钱兑换 II
解决LeetCode上518题“零钱兑换 II”的Python代码示例,采用动态规划方法计算构成给定总金额的不同硬币组合数。
35 2
|
4月前
|
Python
【Leetcode刷题Python】322. 零钱兑换
使用动态规划解决LeetCode上322题“零钱兑换”的Python代码示例,目的是计算构成给定金额所需的最少硬币数量。
38 2
【Leetcode刷题Python】322. 零钱兑换
|
7月前
代码随想录 Day38 完全背包问题 LeetCode T70 爬楼梯 T322 零钱兑换 T279 完全平方数
代码随想录 Day38 完全背包问题 LeetCode T70 爬楼梯 T322 零钱兑换 T279 完全平方数
40 0
|
7月前
|
测试技术
代码随想录 Day37 完全背包理论基础 卡码网T52 LeetCode T518 零钱兑换II T377 组合总和IV
代码随想录 Day37 完全背包理论基础 卡码网T52 LeetCode T518 零钱兑换II T377 组合总和IV
64 0
|
7月前
|
Go
golang力扣leetcode 322.零钱兑换
golang力扣leetcode 322.零钱兑换
40 0
|
7月前
|
Java 索引
leetcode-322:零钱兑换
leetcode-322:零钱兑换
33 0
|
7月前
|
Java
leetcode-518:零钱兑换 II
leetcode-518:零钱兑换 II
51 0
|
7月前
leetcode322零钱兑换刷题打卡
leetcode322零钱兑换刷题打卡
44 0
|
算法
代码随想录算法训练营第四十五天 | LeetCode 70. 爬楼梯、322. 零钱兑换、279. 完全平方数
代码随想录算法训练营第四十五天 | LeetCode 70. 爬楼梯、322. 零钱兑换、279. 完全平方数
83 1
|
算法
代码随想录算法训练营第四十三天 | LeetCode 518. 零钱兑换 II、377. 组合总和 Ⅳ
代码随想录算法训练营第四十三天 | LeetCode 518. 零钱兑换 II、377. 组合总和 Ⅳ
56 1