O(amount * n) O(amount)
Intuition
Process one coin denomination at a time, adding the ways it contributes to each amount. Putting coins on the outer loop counts each combination once (order-independent), avoiding double counting.
Explanation
Why coins on the outside
dp[a] = number of combinations that make amount a. Start with dp[0] = 1 (one way to make 0: pick nothing). For each coin, sweep amounts from coin up to amount and add dp[a - coin].
Looping coins on the outside means a combination like {1,2} is only counted as (use 1s, then 2s) — never also as (2s, then 1s) — so permutations aren't over-counted.
Walk-through
amount = 5, coins = [1,2,5]:
- After coin 1: every amount has 1 way (all 1's).
- After coin 2: dp = [1,1,2,2,3,3].
- After coin 5: dp[5] += dp[0] → 4 combinations: {5}, {1,2,2}, {1,1,1,2}, {1,1,1,1,1}.
Complexity
- Time: O(amount · #coins).
- Space: O(amount).
Implementation
class Solution {
public int change(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];
}
}