Coin Change II
Signals to notice
Brute force first
Recursively try all combinations — exponential without memoization. Many subproblems are re-solved. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DP: dp[j] = number of ways to make amount j. For each coin, update dp left-to-right: dp[j] += dp[j - coin]. Process coins in the outer loop to avoid counting different orderings. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
What must stay true
By processing one coin at a time (outer loop), each combination is counted exactly once in sorted coin order. If coins were in the inner loop, [1,2] and [2,1] would be counted separately. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Easy way to go wrong
Swapping the loop order — coins must be the outer loop. If amount is the outer loop and coins are inner, you count permutations (order matters) instead of combinations (order doesn't). When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.