Greedy vs Dynamic Programming: Key Differences & When to Use
Greedy solves each step with the locally best choice and never looks back; Dynamic Programming (DP) explores all options, stores past results, and guarantees the globally best outcome.
People mix them up because both aim for “best,” but Greedy feels faster—like grabbing the biggest slice of pizza first—while DP looks like extra work until the bill arrives and you realize the slice left you broke.
Key Differences
Greedy: one irrevocable decision per step, O(n log n) typical, works when local equals global optimum. DP: memoized or tabulated sub-problems, O(n²) to O(n³), needs overlapping substructure & optimal subproperty.
Which One Should You Choose?
Pick Greedy for Huffman coding, Kruskal’s MST, or scheduling non-conflicting events. Choose DP for 0/1 knapsack, longest common subsequence, or any problem where yesterday’s choice affects tomorrow’s reward.
Examples and Daily Life
Cashier giving change with the fewest coins? Greedy. Planning the cheapest multi-city flight with stopovers you might revisit? DP. Packing a suitcase once? Greedy. Packing for a month-long tour with laundry constraints? DP.
Can Greedy ever give the wrong answer?
Yes. In the 0/1 knapsack, taking the highest value-to-weight item first can leave unused capacity and a sub-optimal total.
Does DP always beat Greedy in runtime?
No. DP can be slower due to larger state space; Greedy wins when its local rule equals global optimum.
How do I spot overlapping subproblems?
If solving a smaller version of the task repeatedly (like recomputing fib(5)), you’ve found the DP signal.