题目链接

LeetCode

题目描述

给你一个整数数组 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[0]=1。只有当不选取任何硬币时,金额之和才为 0,因此只有 1 种硬币组合。

对于面额为 coin 的硬币,当 coin≤i≤amount 时,如果存在一种硬币组合的金额之和等于 i−coin,则在该硬币组合中增加一个面额为 coin 的硬币,即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins,对于其中的每一种面额的硬币,更新数组 dp 中的每个大于或等于该面额的元素的值。

  • 初始化 dp[0]=1;
  • 遍历 coins,对于其中的每个元素 coin,进行如下操作:
    • 遍历 i 从 coin 到 amount,将 dp[i−coin] 的值加到 dp[i]。
  • 最终得到 dp[amount] 的值即为答案。

上述做法不会重复计算不同的排列。因为外层循环是遍历数组coins 的值,内层循环是遍历不同的金额之和,在计算 dp[i] 的值时,可以确保金额之和等于 i 的硬币面额的顺序,由于顺序确定,因此不会重复计算不同的排列。

  1. class Solution {
  2. public:
  3. int change(int amount, vector<int>& coins) {
  4. vector<int> dp(amount+1);
  5. dp[0] = 1;//一个也不选也是一种方案
  6. for(const int coin : coins){ //nums循环
  7. for(int i=coin;i<=amount;i++){ // target循环
  8. dp[i] += dp[i-coin];//组合问题状态转移方程 dp[i]代表达到金额i的组合数
  9. }
  10. }
  11. return dp[amount];
  12. }
  13. };
  • 时间复杂度 O(nm)
  • 空间复杂度 O(n)