Coin Change & 1D DP Patterns

Coin change asks a slightly harder question than climbing stairs: given a list of coin denominations and a target amount, what is the fewest coins needed to make exactly that amount (or -1 if it cannot be made at all)? Unlike climbing stairs, each step of the recurrence has to consider several possible "previous" amounts - one for every coin denomination - rather than a fixed one or two.

Let dp[i] be the minimum number of coins needed to make amount i. For every amount i from 1 up to the target, and for every coin denomination that is small enough to subtract from i, dp[i] can potentially be built from dp[i - coin] plus one more coin. Taking the minimum over every valid coin gives the best answer for that amount - and once every smaller amount has been solved, i itself can be solved by reusing those answers instead of recursing.

dp is initialized to infinity everywhere except dp[0], which means "not yet known to be reachable." As the loop runs, any amount that actually can be made from some combination of coins gets a finite value written in via the `min`-style comparison, and infinity values simply never win that comparison. If dp[amount] is still infinity once the loop finishes, no combination of coins can make that exact amount, so the function returns -1.

Coin change and climbing stairs look different on the surface, but both were solved with the same three-step recipe - one worth applying to any new 1D DP problem you encounter:

• -Define what dp[i] means in plain language, in terms of the smallest unit of progress the problem has (a step count, an amount, a prefix length).
• -Find the recurrence - how dp[i] can be built from one or more strictly smaller dp[j] values that are already known.
• -Pick the base case(s) - the smallest i where the answer is obvious without needing the recurrence (dp[0] = 0 coins, or n <= 2 steps).
• -Choose the iteration order that guarantees every dp[j] the recurrence depends on is already filled in before dp[i] needs it - almost always smallest-to-largest for these forward-looking dependencies.