Greedy vs DP: When to Use Which Approach

Both greedy algorithms and dynamic programming solve optimization problems, but they are fundamentally different strategies. Choosing the wrong one can lead to incorrect answers or unnecessary complexity. This guide gives you a concrete framework for deciding which to use.

The two key properties

Every optimization problem you encounter in interviews or contests has some combination of these two structural properties.

Optimal substructure

A problem has optimal substructure if the optimal solution to the whole problem contains optimal solutions to its subproblems. Both greedy and DP require this property.

For example, the shortest path from A to C through B must use the shortest path from A to B and the shortest path from B to C. If it did not, you could substitute a shorter sub-path and get a shorter total path, which is a contradiction.

Greedy choice property

A problem has the greedy choice property if a locally optimal choice at each step leads to a globally optimal solution. This is what separates greedy from DP.

When the greedy choice property holds, you never need to reconsider past decisions. You pick the best option right now and move on. When it does not hold, you need DP to explore all possibilities.

When greedy works: activity selection

The activity selection problem is the textbook example of a correct greedy approach. Given a set of activities with start and finish times, select the maximum number of non-overlapping activities.

def activity_selection(activities):
    """
    Greedy: always pick the activity that finishes earliest.
    Time: O(n log n) for sorting
    Space: O(1) extra (ignoring output)
    """
    # Sort by finish time
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_finish = activities[0][1]

    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected


# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
              (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"Selected {len(result)} activities: {result}")
# Selected 4 activities: [(1, 4), (5, 7), (8, 11), (12, 16)]

Why greedy works here: Choosing the earliest-finishing activity leaves the most room for future activities. You can prove this with the exchange argument (covered below).

When greedy fails: coin change

The coin change problem asks for the minimum number of coins to make a target amount. With standard denominations like [1, 5, 10, 25], greedy works perfectly. But with arbitrary denominations, it can fail.

def coin_change_greedy(coins, amount):
    """
    Greedy: always pick the largest coin that fits.
    INCORRECT for arbitrary denominations!
    """
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount <= 0:
            break
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1


def coin_change_dp(coins, amount):
    """
    DP: explore all possibilities.
    Time: O(amount * len(coins))
    Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1


# Standard denominations: greedy works
coins_standard = [1, 5, 10, 25]
print(coin_change_greedy(coins_standard, 30))  # 2 (25 + 5) - correct
print(coin_change_dp(coins_standard, 30))       # 2 - correct

# Arbitrary denominations: greedy FAILS
coins_arbitrary = [1, 3, 4]
print(coin_change_greedy(coins_arbitrary, 6))   # 3 (4 + 1 + 1) - WRONG
print(coin_change_dp(coins_arbitrary, 6))        # 2 (3 + 3) - correct

Why greedy fails: With coins [1, 3, 4] and amount 6, greedy picks 4 first, then needs two 1s for a total of 3 coins. But 3 + 3 = 6 uses only 2 coins. The locally optimal choice (pick the biggest coin) does not lead to the globally optimal answer.

The exchange argument

The exchange argument is the standard technique for proving a greedy algorithm is correct. The steps are:

1. Assume an optimal solution OPT exists.
2. If OPT already follows the greedy strategy, we are done.
3. If not, find the first place where OPT differs from greedy.
4. Show you can exchange the non-greedy choice for the greedy one without making the solution worse.
5. Repeat until OPT matches the greedy solution entirely.

Exchange argument for activity selection

Let G be the greedy solution and OPT be any optimal solution. Suppose the first difference is at position k: greedy picks activity g_k with finish time f(g_k), while OPT picks o_k with finish time f(o_k).

Since greedy always picks the earliest finish time, f(g_k) <= f(o_k). Replace o_k with g_k in OPT. This does not create any conflicts because g_k finishes no later than o_k, so all subsequent activities in OPT remain compatible. The size of the solution stays the same. Therefore OPT with the swap is still optimal, and now it agrees with greedy at position k. Repeat for all positions.

Side-by-side comparison: fractional vs 0/1 knapsack

This is the clearest illustration of when greedy works vs when you need DP.

def fractional_knapsack(items, capacity):
    """
    Greedy: sort by value/weight ratio, take greedily.
    Works because you can take fractions.
    Time: O(n log n)
    """
    # items = [(value, weight), ...]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)

    total_value = 0
    for value, weight in items:
        if capacity <= 0:
            break
        take = min(weight, capacity)
        total_value += take * (value / weight)
        capacity -= take

    return total_value


def knapsack_01_dp(items, capacity):
    """
    DP: must take whole items or nothing.
    Greedy does NOT work here.
    Time: O(n * capacity)
    Space: O(capacity)
    """
    n = len(items)
    dp = [0] * (capacity + 1)

    for value, weight in items:
        # Traverse backwards to avoid using same item twice
        for w in range(capacity, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + value)

    return dp[capacity]


# Example
items = [(60, 10), (100, 20), (120, 30)]  # (value, weight)
capacity = 50

print(f"Fractional knapsack: {fractional_knapsack(items, capacity)}")
# 240.0 (all of item1, all of item2, 2/3 of item3)

print(f"0/1 knapsack: {knapsack_01_dp(items, capacity)}")
# 220 (item2 + item3)

Why the difference? In fractional knapsack, taking a fraction of the best-ratio item is always safe because you can take partial items. In 0/1 knapsack, you might skip a high-ratio item to fit two smaller items that together give more value. The greedy choice of taking the best ratio first is not guaranteed to be globally optimal.

More problems where greedy works

Huffman coding

Build an optimal prefix-free code by always merging the two least-frequent symbols first.

import heapq

def huffman_coding(freq):
    """
    Build Huffman tree greedily.
    Time: O(n log n)
    """
    heap = [[f, [char, ""]] for char, f in freq.items()]
    heapq.heapify(heap)

    if len(heap) == 1:
        heap[0][1][1] = "0"
        return {heap[0][1][0]: "0"}

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)

        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]

        merged = [lo[0] + hi[0]] + lo[1:] + hi[1:]
        heapq.heappush(heap, merged)

    codes = {}
    for pair in heap[0][1:]:
        codes[pair[0]] = pair[1]
    return codes


freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_coding(freq)
for char, code in sorted(codes.items()):
    print(f"  {char}: {code}")

Jump game (can you reach the end?)

def can_jump(nums):
    """
    Greedy: track the farthest reachable index.
    Time: O(n), Space: O(1)
    """
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

More problems where DP is needed

Longest Common Subsequence

def lcs(text1, text2):
    """
    DP: overlapping subproblems prevent greedy approach.
    Time: O(m * n)
    Space: O(min(m, n)) with space optimization
    """
    m, n = len(text1), len(text2)
    if m < n:
        text1, text2 = text2, text1
        m, n = n, m

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]


print(lcs("abcde", "ace"))  # 3 ("ace")

Edit distance

def edit_distance(word1, word2):
    """
    DP: minimum operations to convert word1 to word2.
    Time: O(m * n)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1]   # replace
                )

    return dp[m][n]


print(edit_distance("horse", "ros"))  # 3

Decision framework

Use this checklist when you encounter an optimization problem:

Question	Yes	No
Optimal substructure?	Continue	Neither greedy nor DP
Can you always pick the locally best option?	Try greedy	Use DP
Can you prove the exchange argument?	Greedy is correct	Use DP
Are there overlapping subproblems?	DP will be efficient	Divide and conquer

Quick heuristics

• “Maximize/minimize something with no constraints on choices” - often greedy
• “Count all ways” or “maximize with constraints” - usually DP
• Sorting helps - leans toward greedy
• “At most K” or “exactly K” - usually DP
• Interval scheduling - greedy (sort by end time)
• Subsequence problems - DP

Common mistakes

Mistake 1: Assuming greedy works without proof.

Many problems look like they should work with greedy but do not. Always verify with counterexamples or prove correctness.

# WRONG greedy for job scheduling with profits
# Just because a job has the highest profit doesn't mean
# picking it first is optimal - it might block several
# other profitable jobs.

Mistake 2: Using DP when greedy is sufficient.

If greedy works, it is almost always faster and simpler. Activity selection is O(n log n) with greedy but O(n^2) with DP.

Mistake 3: Confusing “greedy works for a special case” with “greedy works in general.”

Coin change with [1, 5, 10, 25] works with greedy, but the general coin change problem does not.

Complexity comparison

Approach	Time	Space	When to use
Greedy	O(n log n) typical	O(1) typical	Greedy choice property holds
DP (top-down)	O(states)	O(states)	Overlapping subproblems, need memoization
DP (bottom-up)	O(states)	O(states)	Same, but iterative
Brute force	O(2^n) or O(n!)	O(n)	Only for verification

Practice problems

Problem	Approach	Difficulty
Activity Selection	Greedy	Easy
Fractional Knapsack	Greedy	Easy
Jump Game	Greedy	Medium
Huffman Coding	Greedy	Medium
Coin Change	DP	Medium
0/1 Knapsack	DP	Medium
Longest Common Subsequence	DP	Medium
Edit Distance	DP	Medium
Job Scheduling with Deadlines	Greedy	Medium
Minimum Number of Platforms	Greedy	Medium

Key takeaways

1. Both greedy and DP need optimal substructure.
2. Greedy additionally needs the greedy choice property - the local best is the global best.
3. Use the exchange argument to prove greedy correctness.
4. When in doubt, try greedy with counterexamples first. If you find one where greedy fails, switch to DP.
5. Greedy is typically faster (O(n log n)) while DP is typically O(n * k) for some dimension k.