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 a few shared signals mark both of them, and most 1D DP problems, as belonging to this family before you have written a single line of code.

• -The question asks for an optimal value (a minimum or maximum), a count ("how many distinct ways"), or a yes/no reachability ("can this exact total be achieved"), rather than "list every possible solution." If a problem wants every individual solution enumerated, that is usually backtracking (the previous two modules), not DP.
• -A greedy, locally-best choice does not obviously work, or you cannot prove it always leads to the globally best answer (the greedy-choice property from two chapters ahead). DP is the fallback for exactly the cases where greedy cannot be trusted.
• -The problem breaks into smaller versions of itself (optimal substructure), and those smaller subproblems recur across different branches of the naive recursive solution (overlapping subproblems), the same two-part test already used to justify memoization back in Tier 4.
• -You can describe the "state" in one plain sentence: "the fewest coins to make amount i," or "the number of ways to climb to step i." If that sentence has one changing quantity in it, you likely already have your dp[i] definition. Two independent changing quantities point to a 2D grid instead, covered in the next module.

Once a problem is recognized as a DP problem, the same three-step recipe that produced climb_stairs and coin_change applies to any new 1D DP problem you encounter.

• -Define what dp[i] means in plain language, using the state sentence from above.
• -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.