0518. Coin Change I I

518. Coin Change II#

题目 #

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`

解题思路 #

• 此题虽然名字叫 Coin Change，但是不是经典的背包九讲问题。题目中 coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题实际需要计算的是选取硬币的组合数。定义 dp[i] 表示金额之和等于 i 的硬币组合数，目标求 dp[amount]。初始边界条件为 dp[0] = 1，即不取任何硬币，就这一种取法，金额为 0 。状态转移方程 dp[i] += dp[i-coin]，coin 为当前枚举的 coin。
• 可能有读者会有疑惑，上述做法会不会出现重复计算。答案是不会。外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。
• 和此题完全一致的解题思路的题有，第 377 题和第 494 题。

代码 #

``````package leetcode

func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for i := coin; i <= amount; i++ {
dp[i] += dp[i-coin]
}
}
return dp[amount]
}
``````

Nov 25, 2022
Edit this page