Skip to content
Essay · Craft

How to tell if a problem needs greedy or dynamic programming

Choosing between greedy or dynamic programming comes down to whether you can prove the first choice is safe. Here is a repeatable test, a worked coin change example with real numbers, and the signals that point each way.

By Vishy10 min readPublished · 4 Nov 2026

Use greedy when you can prove that a locally best choice never hurts the final answer. Use dynamic programming when that proof fails but optimal substructure and overlapping subproblems remain. Choosing between greedy or dynamic programming comes down to one test: can you defend the first choice without looking at the rest?

The most common failure I see in interviews is not a wrong algorithm. It is a missing argument. Someone sees a minimisation problem, notices that taking the biggest or earliest or cheapest thing looks sensible, writes it in ten lines, and then cannot say why it should be correct. The interviewer produces a four-element counterexample and the whole solution collapses. This essay is about avoiding that moment, and about making the choice with reasoning instead of instinct.

What is the real difference between greedy and dynamic programming?

Greedy commits to one choice at each step and never revisits it, while dynamic programming evaluates every choice for each subproblem, keeps the best, and stores results so no subproblem is solved twice. Both techniques rely on optimal substructure: the best answer to the whole problem contains best answers to smaller pieces. What differs is what you can say about the choices.

Here is the framing I find most useful, and it is the one I wish someone had given me early. Greedy is a dynamic program whose recurrence you have proven can skip all but one branch. Write the brute-force recurrence for any optimisation problem and it looks like best(state) = min over choices of (cost(choice) + best(next state)). Dynamic programming evaluates that min honestly, branch by branch. Greedy replaces the min with a single pick and claims the other branches could not have won. The claim is the entire difference, and a claim needs a proof.

Think of a cashier and an auditor. The cashier hands you change by grabbing the largest coin that fits, never looking back, because the till is designed so that this always works. The auditor keeps a ledger with a row for every sub-amount, because the books are not designed that way and nobody can assume the shortcut holds. Both are doing legitimate work. You just have to know which kind of till you are standing at.

That is also why greedy solutions are shorter and faster but riskier. A dynamic program is wrong only if you wrote the recurrence wrong. A greedy algorithm is wrong if the underlying claim is false, and the code gives you no warning, because it runs and returns plausible answers on most inputs.

How do you test whether a greedy choice is safe?

Attempt an exchange argument: take any optimal solution that does not start with your greedy choice, swap the greedy choice in, and show the result is no worse. If the swap works cleanly, greedy is justified. If you cannot state the swap, or it breaks a constraint, treat greedy as unproven and fall back to a recurrence.

The procedure has four steps:

  1. State the greedy rule precisely, for example "always pick the interval that finishes earliest."
  2. Assume some optimal solution O exists that does not use the greedy pick g as its first element.
  3. Replace the first element of O with g. Check that the result is still feasible.
  4. Check that the objective did not get worse. If both checks pass, there is an optimal solution containing g, and you recurse on what remains.

Take unweighted interval scheduling: pick as many non-overlapping intervals as possible. The rule is earliest finish time first. Suppose the optimal solution starts with interval f, and greedy would choose g, which finishes no later than f. Replace f with g. Everything else in the optimal solution started after f finished, hence after g finished, so nothing overlaps. The count is unchanged. The swap works, so greedy is correct, and the proof fits in four sentences. That brevity is a good sign. If your argument sprawls into case analysis, be suspicious.

Now change one thing: give each interval a weight and maximise total weight instead of count. Take three intervals: A covers 1 to 4 with weight 2, B covers 3 to 10 with weight 10, and C covers 5 to 7 with weight 3. Earliest-finish greedy takes A (ends at 4), skips B because it overlaps, then takes C, for a total of 5. The optimal answer is B alone, worth 10. The exchange argument died at step 4: swapping B out for A made the objective worse, because "finishes earlier" no longer correlates with value. One new field in the input, and a proven algorithm became a wrong one.

The same logic explains why Dijkstra works and why it breaks on negative edges: the invariant that a settled node is final is an exchange argument over paths, and a negative edge is exactly the thing that lets a later path undercut an earlier one.

When the proof is not coming, switch to counterexample hunting. Build inputs of size three or four where the locally best option conflicts with something later. Give yourself two minutes. Most false greedy claims die on an input with three elements, and the ones that survive that are usually true.

Why does greedy fail on coin change?

Greedy fails on coin change because taking the largest coin can leave a remainder that the available denominations pay for badly. With coins of 1, 3 and 4 and a target of 6, greedy takes 4, then 1 and 1, for three coins, while 3 plus 3 needs only two.

Look at why the exchange argument breaks. The optimal solution uses two 3s and no 4. To swap in the greedy 4, you would have to take out coins worth 4 from the optimal set, but there is no subset of {3, 3} that sums to 4. The swap is simply not available, so the proof has nothing to hold. Compare with US coins (1, 5, 10, 25), where the swap always exists. Systems where greedy is optimal are called canonical, and deciding whether an arbitrary system is canonical is itself a nontrivial algorithm. That is why interview problems hand you arbitrary denominations: they want to see whether you assume the cashier's till.

The dynamic programming version commits to nothing. Let dp[a] be the fewest coins that make amount a. Then dp[a] = 1 + min(dp[a - c]) over every coin c that fits.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

def coin_change_greedy(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

Trace the table for coins {1, 3, 4} and amounts 0 through 6. dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1, dp[5]=2 (4 plus 1), dp[6]=2 (3 plus 3). That is 6 amounts times 3 coins, so 18 inner steps. At dp[6] the loop tries 1, 3 and 4 and compares dp[5]+1 = 3, dp[3]+1 = 2, dp[2]+1 = 3. It picks 2. The greedy function never gets to make that comparison, which is the whole problem. Note the second function also has a second bug lurking: it can return -1 on inputs that are actually solvable, such as coins {2, 5, 6} hitting amount 10 via 5 plus 5 only after taking 6 first and getting stuck with 4... which happens to still work here, but the point stands that greedy can both overcount and wrongly report failure.

If you want the full treatment of this problem, with the memoised and tabulated forms side by side, the coin change walkthrough covers it, and memoisation versus tabulation explains the choice of form.

What does dynamic programming cost compared with greedy?

Dynamic programming costs the number of states multiplied by the work per state, while greedy usually costs one sort plus a linear pass. The gap is often smaller than people fear, and sometimes it is enormous, so the real question is how many states your problem has.

For coin change with k coins and target A, the table has A states and each does k comparisons, so the cost is O(A times k) time and O(A) space. At A = 10,000 and k = 3, that is 30,000 steps, which finishes in a few milliseconds even in Python. At A = 10^9 it would need 3 billion steps and a multi-gigabyte array, so the problem as stated would never be set that way unless a different structure existed.

Weighted interval scheduling shows the opposite surprise. With n = 1,000,000 intervals, sorting by end time costs about n log2 n, roughly 20 million comparisons. The dynamic program, best[i] = max(best[i-1], weight[i] + best[pred(i)]), finds each predecessor by binary search, adding another 20 million steps. The total is about 40 million, only twice the greedy cost, and entirely feasible. A naive version that scans backwards for the predecessor is O(n^2), around 10^12 operations, and is hopeless. So the cost of dynamic programming depends on whether you structured the states well, not on the technique itself.

ApproachTime on coin change (amount A, k coins)SpaceWhat you must justifyTypical failure
Greedy (largest coin first)O(k log k) for the sort, then O(k)O(1)Greedy-choice property via an exchange argumentSilently wrong on non-canonical coins, like {1, 3, 4}
Plain recursionUp to O(k^A)O(A) stackOnly the recurrenceTime limit exceeded around A = 30
Memoised DPO(A times k)O(A) table plus stackRecurrence and a base caseStack depth near A on large inputs
Tabulated DPO(A times k)O(A)Recurrence and fill orderOff-by-one on the sentinel value

Notice that greedy is the only row where the effort goes into proof rather than code. Greedy algorithms that rely on ordering often lean on a sort or a priority queue, and when a heap beats sorting is worth knowing for those cases.

Which signals in a problem point toward greedy or dynamic programming?

Signals in the statement and constraints suggest a direction but never prove it. Greedy tends to fit problems with a natural sort key and independent choices, while dynamic programming tends to fit counting, budgets, and choices that consume a shared resource. Use signals to decide what to try first, then verify.

Leaning greedy:

  • The problem is about scheduling, intervals, or merging, and sorting by one field makes the structure obvious.
  • Choices do not interact: taking one item does not change the value of the others, only their availability in a simple way.
  • Input sizes run to 10^5 or 10^6 with no small integer parameter, which rules out a table indexed by value.
  • You can state the rule in one sentence and the counterexample search turns up nothing.

Leaning dynamic programming:

  • The question asks for the number of ways. Greedy almost never counts, because counting requires visiting every option.
  • There is a capacity or budget, such as weight, time, or amount, and choices consume it. This is the knapsack family, covered in knapsack variants.
  • A small integer parameter appears in the constraints: amount up to 10^4, n up to 5,000, length up to 2,000. Those numbers are often the table dimensions in disguise.
  • Your greedy attempt has a counterexample, but the problem still decomposes into smaller copies of itself.

There is a trap in the constraints heuristic. An input bound of 10^5 does not guarantee greedy; some dynamic programs run in O(n log n) with clever state design, as the weighted scheduling example showed. Treat constraints as evidence about the cost you can afford, not about which technique is correct.

What should you do in an interview when you cannot decide?

Write the brute-force recurrence first, then ask whether the minimum or maximum is always attained by one particular branch. If you can argue yes, collapse it to greedy. If not, memoise the recurrence, which gives you a correct dynamic program almost for free.

That ordering matters, and it is the habit I would recommend most. Starting from the recurrence makes the greedy question concrete: "is the branch that takes the largest coin always the winner?" has a definite answer that you can test on {1, 3, 4}. Starting from an intuition and coding it immediately skips the test.

In practice I say it out loud: "My first guess is greedy by finish time. The claim is that the earliest-finishing interval is in some optimal solution. Let me try three intervals with weights to see if it holds." Interviewers rarely penalise a guess that is tested and discarded. They penalise a guess that is defended with nothing. If the test fails, you have already produced the counterexample that justifies the heavier approach, and the transition to the recurrence feels like reasoning rather than retreat.

If dynamic programming is where you end up and it feels shaky, the difficulty is usually in defining the state, not in the code. The essay on why dynamic programming is so hard goes into that, and the dynamic programming topic page collects the standard problems by pattern.

Frequently asked questions

Is greedy always faster than dynamic programming?

Usually, but not always by much. Greedy typically costs a sort plus a linear pass, while dynamic programming costs states times transitions, and on problems like weighted interval scheduling both land at O(n log n). Correctness matters more than the gap, because a fast wrong answer scores zero.

Can a problem be solved by both greedy and dynamic programming?

Yes. Any problem where greedy is provably correct also has a dynamic programming solution, because greedy is a pruned version of the full recurrence. Unweighted interval scheduling and coin change with US denominations are both examples; the dynamic program is just slower than needed.

How do I practise telling them apart?

Take a problem, write the brute-force recurrence, and try to break your greedy guess on inputs of three or four elements before you code anything. Do this on problems where the answer is known to flip, since the contrast teaches the most. A good place to start is Coin Change.