LeetCode 518 · Medium · 2-D Dynamic Programming

Coin Change II

With an unlimited supply of each coin value, count how many different combinations of coins add up to amount. Order does not matter: 1+2 and 2+1 are the same combination.

O(n·amount)time
O(amount)space
skip + reusecoins × amounts table

amount: 0 to 10 · coins: 1–4 distinct values, each 1 to 10

+=

ways row = coins from this one down · column = amount · ∅ = no coins

public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; // no coins dp[0] = 1; for (int i = coins.length - 1; i >= 0; i--) { int[] nextDP = new int[amount + 1]; nextDP[0] = 1; for (int a = 1; a <= amount; a++) { nextDP[a] = dp[a]; // skip coin i if (a - coins[i] >= 0) { nextDP[a] += nextDP[a - coins[i]]; } } dp = nextDP; } return dp[amount];}
i, coins[i]
—
a
—
dp[a]
—
nextDP
—

Why it works

  1. Brute force recurses on (coin, remaining amount) and either uses the coin again or moves past it for good. Without a cache the same pairs repeat, and the call count grows exponentially with the amount.
  2. Each combination is counted once because coins are decided in a fixed order. Row i may use coins[i] and anything below it. So ways(i, a) = ways without coin i (the cell below) + ways that use at least one more coin i (the cell coins[i] to the left, same row).
  3. Complexity: n coin rows × (amount+1) cells, O(1) each: O(n·amount) time. Each row reads only itself and the row below, so two rows of amount+1 numbers suffice: O(amount) space.
  4. Pitfall: looping amounts outside and coins inside counts orders, not combinations (1+2 and 2+1 twice): that is Combination Sum IV. And dp[0] = 1: there is exactly one way to make 0, take nothing.
  5. Related: Coin Change (322) asks for the fewest coins, so its cell is a min instead of a sum. One 1-D array updated left to right also works here, because the same row is meant to be reused.