Pattern Recognition Drill
Medium 2-D Dynamic Programming
The Problem
Given coins and an amount, find the number of WAYS to make the amount (unlimited supply).
What approach would you use?
Think about it before scrolling down.
dp[a] += dp[a - coin] for each coin. Outer loop on coins avoids counting permutations. O(amount * coins).
Same. The key insight is coin-first loop gives combinations, not permutations.
Common Trap
If you iterate amounts in the outer loop, you count permutations (1+2 and 2+1 as different). Coins first = combinations.