518. 零钱兑换 II

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]

Output: 4

Explanation: there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]

Output: 0

Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]

Output: 1

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

题目大意

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

解题思路

思路一：动态规划

• 使用二维数组 dp，其中 dp[i][j] 表示在前 i 种硬币中凑成金额 j 的组合数。

• 初始化第一列，表示凑成金额为 0 的组合数都为 1。

• 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]

  • 其中，coins[i - 1] 表示第 i 种硬币的面值。

• 遍历硬币种类和金额，根据状态转移方程更新 dp[i][j] 的值。

  • 对于每一种硬币 coins[i - 1]，遍历金额 j。
  • 如果 j - coins[i - 1] >= 0，则更新 dp[i][j] 的值，否则保持 dp[i][j] 不变。

复杂度分析

• 时间复杂度：O(n * amount)，其中 n 是硬币的种类。
• 空间复杂度：O(n * amount)，使用了一个二维动态规划数组。

---

思路二：压缩状态的动态规划

• 使用一维数组 dp，其中 dp[j] 表示凑成金额 j 的组合数。

• 初始化 dp[0] 为 1，表示凑成金额为 0 的组合数为 1。

• 状态转移方程：dp[j] += dp[j - coin]，其中，coin 表示当前硬币的面值。

• 遍历硬币种类和金额，根据状态转移方程更新 dp[j] 的值。

  • 对于每一种硬币 coin，遍历金额 j。
  • 如果 j - coin >= 0，则更新 dp[j] 的值。

复杂度分析

• 时间复杂度：O(n * amount)，其中 n 是硬币的种类。
• 空间复杂度：O(amount)，使用了一个一维动态规划数组。

代码

动态规划

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
	const n = coins.length;
	const dp = new Array(n + 1).fill(0).map(() => new Array(amount + 1).fill(0));
	for (let i = 0; i <= n; i++) {
		dp[i][0] = 1;
	}
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= amount; j++) {
			if (j - coins[i - 1] >= 0) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	return dp[n][amount];
};

压缩状态的动态规划

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
	const dp = new Array(amount + 1).fill(0);
	dp[0] = 1;
	for (let coin of coins) {
		for (let j = 1; j <= amount; j++) {
			if (j - coin >= 0) {
				dp[j] += dp[j - coin];
			}
		}
	}

	return dp[amount];
};

相关题目

题号	标题	题解	标签	难度
2218	从栈中取出 K 个硬币的最大面值和		数组 动态规划 前缀和
2585	获得分数的方法数		数组 动态规划
2902	和带限制的子多重集合的数目		数组 哈希表 动态规划 1+
2915	和为目标值的最长子序列的长度		数组 动态规划
3183	达到总和的方法数量 🔒		数组 动态规划