Coin Change II

leetcode_518.md

Description

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.

Link to the original problem

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

Constraints:

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

Idea

1. It's a fairly easy question, but it is an excellent introduction to a faily important algorithmic pattern, i.e., Dynamic Programming (DP).
2. Assume you worked on DP problems before, you are probably familiar with the concepts likes "base case", "state" and "formula", let's forget about that for now and see how we can achieve that.
3. Btw, when you see a statement like "return the number of combinations ...", that's a good signal to try DP first.
4. Let's see we can do for this problem.
5. So we want to find out how to make amount with different unique coins.
6. Let's take the first example, where coins = [1,2,5] and amount = 5.
7. So to make a 5, we can grab a coin 5, that's one way and only way with a coin 5. Easy.
8. Is there another way to make 5 though? Yep, since we have a coin 1, if we can make a 4 in X number of ways, then we know we can get a 5 in X more number of ways.
9. Similarly, since we have a coin 2, if we can make a 3 in Y number of ways, we know we can get a 5 in Y more number of ways.
10. I believe you probably spot a pattern now, which is, if we define dp[amount] to be "number of ways to get amount", then dp[amount] = dp[amount] + dp[amount - coin] for coin in coins.
11. And how do we get dp[amount - coin]? Actually, it's the same question. Assume amount - coin = i, we have dp[i] = dp[i] + dp[i - coin] for coin in coins.
12. And initially, dp should be initialized with all 0s, except dp[0] = 1, because that's what we have at the beginning, so no surprise.
13. At last we should return dp[amount], that's it.
14. It should be fairly easy now to write the code. Let me know if it does not make sense to you.
15. Thanks for reading, :).

Solution

Javascript

// dp[i]: different ways to make up amount i
// dp[i] = dp[i] + dp[i - coin] for coin in coins
const change = function(amount, coins) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; i += 1) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[dp.length - 1];
};

References

1. Dynamic Programming