Greedy vs Dynamic Programming
The Cashier Coin Trap and Proving the Greedy Choice Property
How to tell when making the best local choice right now is globally optimal, versus when choices interact and require dynamic programming.
"Does making the locally optimal choice right now guarantee you will never regret it later, or can an early choice paint you into a suboptimal corner?"
Ask this single question during the first two minutes of reading the problem prompt. The answer decides your fundamental pattern.
A chai stall cashier makes change for customers. With standard Indian currency coins (Rs 1, Rs 2, Rs 5, Rs 10), a greedy strategy works every single time: always hand back the largest denomination possible. If change is Rs 7, you give Rs 5 and Rs 2. You never get a suboptimal coin count. But imagine the stall owner introduces promotional tokens worth Rs 1, Rs 3, and Rs 4. A customer needs Rs 6 in change. The greedy cashier grabs the largest coin first: Rs 4. That leaves Rs 2, which requires two Rs 1 coins (4 + 1 + 1 = 3 coins). But another customer hands over two Rs 3 tokens: exactly Rs 6 in only 2 coins (3 + 3 = 2)! The greedy cashier got painted into a corner because picking the biggest coin early locked out the optimal pair.
When to Choose Which Pattern
Greedy Algorithms
Option A- ✓The problem has the greedy choice property: a global optimum can be reached by selecting the locally best choice at each step without backtracking.
- ✓Optimal substructure: an optimal solution to the problem contains optimal solutions to subproblems.
- ✓Decisions are irreversible: once you make a choice, you never need to reconsider.
- ✓Sorting or scanning the input lets you lock in decisions one by one.
Dynamic Programming
Option B- ✓Subproblems overlap: solving subproblem A requires answers to smaller subproblems that are also needed by subproblem B.
- ✓Choices interact: taking an item or coin now limits future decisions, so multiple paths must be compared.
- ✓Optimization over combinations: finding min, max, or count across non-canonical values.
- ✓Greedy fails on counterexamples.
Side-by-Side Worked Examples
Compare concrete implementations side by side to see how the code structure diverges.
Jump Game(LC 55)
LeetCode ↗Maintain max_reachable index. As you iterate through index i, if i > max_reachable, you are stranded. Otherwise, update max_reachable = max(max_reachable, i + nums[i]). You never care which specific jump brought you to an index, only the maximum reach boundary. This local greedy extension guarantees finding whether the end is reachable.
def canJump(nums: list[int]) -> bool:
max_reachable = 0
for i, jump in enumerate(nums):
if i > max_reachable:
return False
max_reachable = max(max_reachable, i + jump)
return TrueCoin Change(LC 322)
LeetCode ↗Let dp[a] be the minimum coins needed to make amount a. For each amount from 1 to target, try every available coin denomination: dp[a] = min(dp[a - coin] + 1) for coin <= a. Because arbitrary denominations lack the greedy choice property, DP explores all overlapping choices systematically.
def coinChange(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
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] != float('inf') else -1The Decision Matrix
Choice Reversibility
Permanent, never reconsidered or backtracked
Considers all valid choices and takes the minimum or maximum
Subproblem Overlap
Subproblems do not overlap; only one branch is followed
Subproblems overlap heavily; results are memoized or tabulated
Runtime Complexity
Usually O(N) or O(N log N)
Polynomial O(N * W), O(N^2), or pseudo-polynomial
Proof Requirement
Requires formal exchange argument or matroids proof
Requires defining state variables and recurrence relation
| Evaluation Factor | Greedy Algorithms | Dynamic Programming |
|---|---|---|
| Choice Reversibility | Permanent, never reconsidered or backtracked | Considers all valid choices and takes the minimum or maximum |
| Subproblem Overlap | Subproblems do not overlap; only one branch is followed | Subproblems overlap heavily; results are memoized or tabulated |
| Runtime Complexity | Usually O(N) or O(N log N) | Polynomial O(N * W), O(N^2), or pseudo-polynomial |
| Proof Requirement | Requires formal exchange argument or matroids proof | Requires defining state variables and recurrence relation |
Where Candidates Go Wrong (Top Traps)
Assuming Greedy works because it passes small examples on paper
Using 2D DP when a greedy single-pass reachability scan works
Confusing Fractional Knapsack with 0/1 Knapsack
Related Walkthroughs in our DSA Course
Explore step-by-step solutions with 4-language code flaps (Java, C#, TS, Python) and visual memory dry runs.
Non-overlapping Intervals (Greedy Interval Scheduling)
Partition Equal Subset Sum (0/1 Knapsack DP)
Longest Increasing Subsequence (DP State Evolution)
"Greedy delivers O(N) speed and O(1) memory, but gives up safety unless the greedy choice property is mathematically proven. Dynamic Programming guarantees global optimality across interacting choices, but trades away memory for state tables."
Practice Real Indian Hiring Loops
See the exact problems asked at Flipkart, Swiggy, Razorpay, PhonePe, and Amazon with verified candidate reports and round structures.