Greedy vs. DP: The 30-Second Test for Coin Change Problems

Source: Dev.to

Originally published on LeetCopilot Blog

TL;DR

• Topic: Deciding whether to use greedy or DP for coin‑change variants.
• Why it matters: Picking the wrong strategy wastes time and confuses interviewers.
• Core steps: Check coin‑system properties, test a counterexample, fall back to DP when optimal substructure is unclear.
• Key insight: Canonical coin systems are the exception, not the rule.
• You’ll learn: A quick heuristic, a TypeScript DP snippet, and practice drills.

Beginner‑Friendly Explanations

When Greedy Works

Greedy is safe when the coin system is canonical—each larger coin is a multiple or a structured combination of smaller ones.
Example: USD coins (1, 5, 10, 25) are canonical for making change with the fewest coins.

When Greedy Fails

If a larger coin is not composed of smaller ones, greedy can pick a locally good coin that ruins the global optimum.
Example: Coins [1, 3, 4], target 6. Greedy picks 4 + 1 + 1 (3 coins) instead of 3 + 3 (2 coins).

Why DP Rescues You

DP explores all sub‑targets. Bottom‑up tabulation guarantees the minimum number of coins if you define a recurrence like

dp[x] = min(dp[x - c]) + 1   for every coin c

Visual Concept

Imagine two columns: Greedy path (choose biggest, subtract, repeat) versus DP table (fill from 0 to target). The DP column never forgets a better sub‑solution.

Step‑by‑Step Learning Guidance

1) Run the Counterexample Test

Before coding, test a small counterexample in your head: try making 6 with coins [1,3,4]. If greedy fails, you must use DP. This fast check helps you explain your reasoning clearly, similar to the approach in greedy algorithm counterexamples for coding interviews.

2) Decide the State and Transition

For minimum coins, the state is the target amount. Transition checks every coin:

dp[x] = Math.min(dp[x], dp[x - coin] + 1)   // when x - coin >= 0

3) Handle Impossible States

Initialize all entries to Infinity except dp[0] = 0. If dp[target] stays Infinity, return -1.

4) Talk Through Complexity

Mention that the bottom‑up approach is O(n × amount) time and O(amount) space. Interviewers like hearing that you know the trade‑offs.

5) Practice With Two Targets

Solve for 6 and 27 with coin sets [1,3,4] and [1,5,10,25]. Compare greedy and DP answers to cement the heuristic.

Visualizable Example: Bottom‑Up Coin Change in TypeScript

function minCoins(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let total = 1; total = 0) {
        dp[total] = Math.min(dp[total], dp[total - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

Each total reuses the best sub‑target solutions, which greedy might miss.

Practical Preparation Strategies

Build Your Own Decision Table

Create a two‑column sheet: coin sets where greedy works, and coin sets where it fails. Add a short note for each. Review this alongside how to know when dynamic programming is needed to strengthen pattern recognition.

Drill Under a Timer

Give yourself five minutes to classify and solve three random coin systems. Pressure makes the heuristic stick.

Use Light Guidance

Assistants like LeetCopilot can prompt you to present the counterexample before you start coding, reinforcing disciplined reasoning without giving away the DP.

Connect to Other Patterns

Notice how this mirrors sliding‑window decisions: pick greedy only when monotonic properties hold. The sliding window visualizer trains that instinct of watching invariants.

Common Mistakes to Avoid

Assuming USD Rules Apply Everywhere

Foreign or custom coin systems often break greedy assumptions.

Forgetting Initialization

Leaving dp at zero by default incorrectly favors impossible states.

Ignoring Negative or Zero Coins

Validate input; coins should be positive, or your loop can spin forever.

Not Returning -1 for Impossible Targets

Interviewers expect a clear signal when no combination exists.

FAQ

How do I know greedy is valid?
Try a small counterexample. If greedy ever uses more coins than an alternative, switch to DP.

What should I practice before coin change?
Basic loops, array initialization, and thinking in subproblems. Then learn to explain the recurrence.

Is this topic important for interviews?
Yes. It tests pattern selection, not just coding ability.

Can I optimize the DP further?
Yes—use one‑dimensional arrays as shown, and prune coins greater than the target to reduce work.

Conclusion

Choosing between greedy and DP for coin change comes down to proving or disproving the coin system’s structure. Lead with a counterexample, fall back to DP when unsure, and communicate your reasoning. With practice, this decision becomes automatic and interview‑safe.

If you’re looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.