Greedy vs DP: When to Use Each
Identify the hallmarks of problems solvable by greedy versus those requiring DP using the greedy-choice property and exchange argument.
Greedy and DP Overview
Both Greedy and Dynamic Programming solve optimisation problems — finding a maximum, minimum, or optimal arrangement. Greedy makes the locally optimal choice at each step without reconsidering previous decisions. DP explores all possibilities but uses memoisation to avoid recomputation. Knowing which to apply can save hours of debugging an incorrect greedy or a needlessly complex DP table.
# Greedy: always take the locally best option
# Example: coin change with coins [1, 5, 10, 25]
# Greedy: take as many 25s as possible, then 10s, etc.
# This works for standard denominations but NOT all coin sets!
# DP: explore all possibilities via memoisation
# Example: coin change with coins [1, 3, 4] and target 6
# Greedy would pick 4, then 1, 1 → 3 coins
# DP finds: 3 + 3 → 2 coins (optimal!)
print('Greedy can fail when local optimum != global optimum')The Greedy Choice Property
A problem has the greedy choice property when a globally optimal solution can always be constructed by making locally optimal (greedy) choices. Formally: there exists an optimal solution that begins with the greedy choice, so we never need to backtrack. Proving this typically uses an exchange argument: assume any optimal solution does not include the greedy choice, then show you can swap it in without making things worse.
# Exchange argument example: Activity Selection
# Greedy: always pick the activity that ends earliest
# Proof: suppose optimal solution starts with activity A (not earliest-ending)
# Let G be the earliest-ending activity.
# Replace A with G in the solution:
# - G ends no later than A, so G does not conflict with any activity A allowed
# - The solution remains valid with at least as many activities
# Therefore greedy choice (earliest end) is always safe.
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
activities.sort(key=lambda x: x[1]) # sort by end time
print('Sorted by end:', activities[:4], '...')All lessons in this course
- Greedy vs DP: When to Use Each
- Interval Scheduling and Merging
- Jump Game I and II
- Task Scheduler and Gas Station