Recognizing greedy vs DP
Overview
The single highest-value diagnostic skill: differentiating between problems that can be solved with a fast Greedy approach versus those requiring exhaustive Dynamic Programming.
Both patterns optimize for a maximum or minimum answer. If you use DP when Greedy works, you waste massive memory and time. If you use Greedy when DP is required, your algorithm will confidently return the wrong answer because it gets trapped in local maxima.
Where used: Network routing (BGP/OSPF) uses Dijkstra's greedy approach because non-negative latency guarantees local choices are globally optimal., Content-aware image resizing (Seam Carving) requires DP; a greedy pixel choice might force the seam through the main subject.
Why learn this
- It operationalizes a strict decision procedure: (1) Does an exchange argument prove local choices never foreclose better global outcomes? If yes, Greedy. (2) If choices foreclose paths, are there overlapping subproblems? If yes, DP.
- It proves that recognizing patterns requires analyzing precise constraints, not just 'vibes' (e.g., Fractional Knapsack is Greedy; 0/1 Knapsack is DP).
Common mistakes
- Assuming 'sounds greedy' is sufficient justification: It never is. Without a mathematical exchange argument proving that a greedy choice is always safe, you are just guessing. If a choice CAN foreclose a better outcome, Greedy fails.
- Jumping to DP without checking for a greedy proof: DP is overkill for simple matroids. Always check if a greedy choice is mathematically viable before committing to building O(n^2) memoization tables.
Recall questions
- What is the core prerequisite required to safely use a Greedy algorithm?
- Why does the 0/1 Knapsack problem require Dynamic Programming, while the Fractional Knapsack can be solved with a Greedy algorithm?
Understanding checks
You are given a list of meetings with start and end times and asked to find the maximum number of non-overlapping meetings you can attend. Do you need DP to explore all combinations, or can you use a Greedy approach?
You can use a Greedy approach (sort by earliest end time). The exchange argument holds: picking the meeting that ends earliest leaves the maximum possible free time for any subsequent meetings. It never forecloses a better total count.
Interval scheduling is the canonical example of a problem that looks like it requires combinatorial exploration (DP) but is mathematically solvable via Greedy.
A student attempts to solve the 'Coin Change' problem (finding the minimum number of coins to make a target amount) using a Greedy approach: always picking the largest coin possible first. Will this always work?
No. It fails if the coin denominations are not canonical. For example, with coins [1, 3, 4] and a target of 6, Greedy picks [4, 1, 1] (3 coins), but the optimal DP solution finds [3, 3] (2 coins).
This is the classic failure signal of Greedy. The local optimal choice (picking 4) foreclosed the global optimal path (picking two 3s). Overlapping subproblems demand DP here.
Practice tasks
Greedy failure demonstration
Modify the given greedy coin change algorithm to instead return a boolean indicating whether the greedy approach yielded the optimal result compared to the provided DP answer, for the inputs coins=[1, 3, 4], target=6.
Continue learning
Previous: Why greedy works
Previous: Why greedy fails
Previous: Overlapping subproblems
Previous: Optimal substructure