Coin Change and Spotting DP

Fibonacci and climbing stairs are gentle: there is one number to compute and the recurrence is handed to you. Real DP problems are about finding the best option among many, and this is where the technique earns its reputation. Coin change is the classic first real one.

The problem, and why greedy is not enough

Given coin denominations and a target amount, what is the fewest coins that add up to the amount? With US-style coins [1, 5, 10, 25], a natural instinct is to be greedy: keep taking the biggest coin that fits. For everyday coins that happens to work - but it is not a general rule, and it is easy to break.

Take coins [1, 3, 4] and amount 6. Greedy grabs the 4, leaving 2, then two 1s: that is 4 + 1 + 1, three coins. But 3 + 3 is two coins. Greedy walked confidently to the wrong answer because a locally biggest choice can force worse choices later.

DP fixes this by considering every first coin and trusting the smaller answers.

def coin_change(coins, amount):
    INF = amount + 1                     # a stand-in for "impossible", larger than any real answer
    dp = [0] + [INF] * amount            # dp[a] = fewest coins to make amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 3, 4], 6))         # greedy would say 3; the truth is 2
print(coin_change([1, 5, 10, 25], 63))
print(coin_change([2], 3))               # odd amount, only even coins -> impossible

2
6
-1

What just happened: dp[a] holds the fewest coins to make amount a. To fill it, we try every coin c that fits and ask: "what if this coin is the last one I add?" That leaves a - c to make, whose best answer is already sitting in dp[a - c], so the candidate is dp[a - c] + 1. Take the smallest candidate over all coins. Amounts that can never be formed keep the INF sentinel and report -1. This runs in O(amount * number_of_coins).

💡 Key point. The greedy version commits to one coin and never looks back. DP tries every possible last coin and lets the already-solved subproblems decide which one leads to the best total. That willingness to consider all first moves, backed by cached answers, is what makes it correct where greedy is not.

How to recognize a DP problem

You will not always be told "this is dynamic programming." Two properties, present together, are the tell:

• Optimal substructure. The best answer to the whole problem can be built from the best answers to its subproblems. In coin change, the best way to make 6 is "one more coin than the best way to make 6 - c" for the right choice of c. If the pieces of an optimal solution are themselves optimal, you have it.
• Overlapping subproblems. The same subproblems come up repeatedly, so caching pays off. If every subproblem were unique, you would just have plain recursion (like merge sort) and DP would add nothing.

📝 Terminology. A problem with optimal substructure but no overlap is usually a divide-and-conquer problem, not DP. A problem with overlap but no optimal substructure (where a locally best choice can be undone later in a way caching cannot capture) may not be solvable by DP at all. You need both.

⚠️ Gotcha. Greedy and DP can agree on some inputs and disagree on others, as the two coin sets above showed. "It worked on my examples" is not proof a greedy shortcut is correct. When the problem asks for an optimum and choices interact, reach for DP unless you can prove greedy is safe for your specific coin system.

The recipe

Once you suspect DP, the steps are always the same:

1. Define the subproblem precisely - what does dp[i] (or dp[i][j]) mean?
2. Write the recurrence - how is dp[i] built from smaller entries?
3. Set the base cases - the smallest inputs whose answers you know outright.
4. Choose a direction - top-down memoization or bottom-up tabulation.
5. Read the answer out of the table.

Nail step 1 and the rest tends to follow. A vague subproblem definition is the single most common reason a DP attempt stalls.

Check yourself

[
  {
    "q": "Why does greedy 'always take the biggest coin' fail for coins [1, 3, 4] and amount 6?",
    "choices": ["Greedy is never correct for any problem", "Greedy takes 4 + 1 + 1 (three coins), but 3 + 3 (two coins) is better", "6 cannot be made from those coins at all", "Greedy and DP give the same answer here"],
    "answer": 1,
    "explain": "Grabbing the biggest coin (4) forces two 1s afterward for three coins total, while 3 + 3 needs only two - a locally biggest choice led to a worse overall result."
  },
  {
    "q": "In the coin-change table, what does dp[a] represent?",
    "choices": ["The number of coins whose value equals a", "The fewest coins needed to make amount a", "Whether amount a is even", "The largest coin not exceeding a"],
    "answer": 1,
    "explain": "dp[a] is the minimum number of coins that sum to a; the algorithm fills it by trying each coin as the last one added."
  },
  {
    "q": "Which two properties together signal that a problem is a good fit for dynamic programming?",
    "choices": ["Recursion and loops", "Sorting and searching", "Optimal substructure and overlapping subproblems", "Large inputs and small outputs"],
    "answer": 2,
    "explain": "Optimal substructure means the best whole answer is built from best sub-answers; overlapping subproblems means those sub-answers repeat, so caching them pays off. DP needs both."
  }
]