Coin Change — Number of Ways

Recurrence

int countWays(int amount, int[] coins) {
  int[] dp = new int[amount + 1];
  dp[0] = 1;
  for (int coin : coins)
    for (int a = coin; a <= amount; a++)
      dp[a] += dp[a - coin];
  return dp[amount];
}

Why coin outer loop

Ensures distinct combinations only. If amount outer: counts permutations (different orderings).

Number of coins variant

Change amount outer loop convention. dp[a] = min coins to make a. Init dp = ∞, dp[0] = 0.

Applications

Vending machines. Currency exchange. Numerical partitions in number theory.