Dynamic Programming • Unbounded Knapsack

Coin Change II (Number of Ways)

Find the total number of combinations that make up a given amount using given coins.

Overview

This is a combinatorics variant of the unbounded knapsack problem. Instead of minimizing, we are summing all distinct ways to form amounts.

Let `dp[i]` be the number of ways to make amount `i`. Initially, `dp[0] = 1` (doing nothing is 1 way).

For each coin, any amount `i` can be reached by adding the coin to amount `i - coin`. So we add `dp[i - coin]` to `dp[i]`.

Iterating coins on the outer loop guarantees we only consider combinations (ignoring order) rather than permutations.

Coins:Amount:

dp[0]1

dp[1]0

dp[2]0

dp[3]0

dp[4]0

dp[5]0

Code Tracker

:::

1let dp = Array(amount + 1).fill(0); dp[0] = 1;

2for (let coin of coins) {

3 for (let i = coin; i <= amount; i++) {

4 dp[i] += dp[i - coin];

5 }

6}