Coin Change

Difficulty: Medium

Problem

You're given coin denominations — with an UNLIMITED supply of each — and a target amount. Return the FEWEST coins whose values sum to amount exactly. If no combination of coins can make the amount, return -1. This is the problem where the 'obvious' greedy idea (always grab the biggest coin) meets its famous counterexample — and dynamic programming takes the case.

Example

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1: three coins. No two coins can do it — the best pair, 5 + 5, stops at 10 — so 3 is the minimum.

Brute-force approach

No separate brute-force phase — the exponential try-every-last-coin recursion IS Step 1 of the guided walkthrough, where it gets diagnosed and upgraded into the memo and then the table.

Optimal approach

Key insight: Every way to make amount a ends with some final coin c. Try each: 1 + fewest for (a − c). The minimum over all final coins is dp[a] — greedy guessing replaced by exhaustive-but-cached trying.

Build dp[a] = fewest coins making amount a exactly, from 0 up to amount. Each amount auditions every coin as its possible FINAL coin and keeps the cheapest option; ∞ marks amounts no combination has reached, and a surviving ∞ becomes -1.

Steps

  1. Define the state: dp[a] = fewest coins that sum to a exactly (∞ = not makeable so far)
  2. Seed dp[0] = 0 — zero coins make amount zero — and every other slot ∞
  3. For each amount a from 1 to amount, audition every coin c ≤ a as the LAST coin
  4. Each audition costs 1 + dp[a − c]; keep the minimum across all coins
  5. Return dp[amount], converting a surviving ∞ into -1

Time complexity: O(amount × coins) · Space complexity: O(amount)