What is the difference between greedy and dynamic programming approaches?
Updated Feb 20, 2026
Short answer
Both require optimal substructure, but greedy commits to one locally-best choice at each step and never reconsiders, while dynamic programming evaluates every choice and reuses stored results for overlapping subproblems. Greedy is faster — typically O(n log n) against DP's O(n·W) — but only correct when the greedy-choice property holds. When it does not, DP gives the right answer at higher cost.
Deep explanation
| Greedy | Dynamic programming | |
|---|---|---|
| Choices per step | one, irrevocable | all, then pick the best |
| Needs optimal substructure | yes | yes |
| Needs greedy-choice property | yes | no |
| Needs overlapping subproblems | no | yes, that is the point |
| Typical complexity | O(n log n) | O(n·W) or O(n²) |
| Memory | O(1) | O(n) or O(n·W) |
The distinguishing requirement is the greedy-choice property. Both need optimal substructure — an optimal solution built from optimal sub-solutions. Only greedy additionally needs that the locally best choice is safe. DP does not, because it tries every choice and lets the recurrence decide.
The 0/1 knapsack shows the contrast directly:
# DP: try both choices for every item, at every capacitydef knapsack(items, capacity): dp = [0] * (capacity + 1) for value, weight in items: for c in range(capacity, weight - 1, -1): # backwards: each item once dp[c] = max(dp[c], # skip this item dp[c - weight] + value) # take it return dp[capacity]The max is exactly what greedy lacks. Greedy would pick by value/weight ratio and commit; DP keeps both branches alive until the end.
Overlapping subproblems is DP's other requirement and the reason memoisation pays. Naive recursive Fibonacci recomputes fib(30) millions of times; DP computes it once. If subproblems do not overlap — as in mergesort, where each half is distinct — you have divide and conquer, not DP.
How to choose in practice. Start by asking whether a greedy criterion can be proved by an exchange argument. If yes, take it: less code, less memory, better complexity. If you can construct a counterexample, reach for DP. If you can do neither quickly, write the DP — a correct slow answer beats a fast wrong one, and you can optimise later.
Some problems admit both at different granularities. Fractional knapsack is greedy; 0/1 knapsack is DP. Same domain, and indivisibility is the entire difference.
Real-world example
Coin change, where the two diverge on the same input:
coins, target = [1, 3, 4], 6
# Greedy: take the largest coin that fits, repeatedly# 4 -> remaining 2 -> 1 -> 1 = 3 coins WRONG
def min_coins(coins, target): # DP: correct for any denominations dp = [0] + [float('inf')] * target for t in range(1, target + 1): for c in coins: if c <= t: dp[t] = min(dp[t], dp[t - c] + 1) return dp[target]
min_coins([1,3,4], 6) # 2 (3 + 3) CORRECTGreedy commits to the 4 and can never recover; DP evaluates both branches at every amount. The cost is O(target × len(coins)) instead of O(target/largest_coin) — real, but the greedy answer here is simply wrong.
Common mistakes
- - Assuming that optimal substructure alone justifies greedy
- the greedy-choice property is the additional requirement and the one that usually fails.
- - Reaching for DP where greedy is provably optimal, paying unnecessary time and memory — minimum spanning trees do not need DP.
- - Applying DP without overlapping subproblems, which is divide and conquer with extra bookkeeping and no benefit.
- - Iterating the 0/1 knapsack capacity loop forwards, which allows an item to be used more than once and silently solves the unbounded variant instead.
- - Assuming a greedy solution that passes the given tests is correct, when a counterexample often exists just outside them.
- - Forgetting DP's memory cost
- a large capacity dimension can make the table impractical without rolling-array optimisation.
Follow-up questions
- What exactly is the greedy-choice property?
- Why must the 0/1 knapsack inner loop run backwards?
- What distinguishes dynamic programming from divide and conquer?
- Can a problem have both a greedy and a DP solution?