Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 518 Coin Change II - Loop Order

The fix

Wrong (counts permutations):

for a from 1 to amount
    for each coin in coins
        dp[a] += dp[a - coin]

Correct (counts combinations):

for each coin in coins
    for a from coin to amount
        dp[a] += dp[a - coin]

In the correct version, you fully process coin 1 before touching coin 2. Every combination is counted exactly once in a canonical order. Take time to understand this concept thoroughly. Work through small examples by hand. The pattern will become clear with practice. Once you internalize it, you will recognize similar problems immediately.