Greedy vs DP How to Know Which to Apply in DSA Python - Trade-offs & Analysis

Mental Model

Greedy picks the best choice now, hoping it leads to the best overall. DP tries all choices and remembers results to find the best overall.

Analogy: Choosing snacks: greedy is like grabbing the tastiest snack first without thinking ahead; DP is like planning all snacks to get the tastiest total combination.

Choices: [1] [2] [3]
Greedy: pick best now -> [1] -> next best -> can't
DP: explore all combos -> [2,3] -> pick best total

Dry Run Walkthrough

Input: weights = [6, 5, 5], values = [30, 20, 20], capacity = 10

Goal: Decide if greedy or DP works better to maximize value without exceeding capacity

Step 1: Greedy picks item with highest value/weight ratio first (item 1: value 30, weight 6)

Picked: [1], Remaining capacity: 4

Why: Greedy tries best immediate value per weight

Step 2: Greedy tries to pick next best ratio item (item 3: value 20, weight 5) but capacity 4 is too small

Picked: [1], Remaining capacity: 4

Why: Cannot pick item 3 due to capacity limit

Step 3: Greedy ends with total value 30

Picked: [1], Total value: 30

Why: No more items fit

Step 4: DP tries all combinations: picks items 2 and 3 (weights 5+5=10, values 20+20=40)

Picked: [2,3], Total value: 40

Why: DP finds better total value by combining items

Result:

DP picks [2,3] with total value 40, better than greedy's 30

Annotated Code

DSA Python

class Knapsack:
    def __init__(self, weights, values, capacity):
        self.weights = weights
        self.values = values
        self.capacity = capacity

    def greedy(self):
        ratio = [(v / w if w != 0 else float('inf'), i) for i, (v, w) in enumerate(zip(self.values, self.weights))]
        ratio.sort(reverse=True)
        total_value = 0
        total_weight = 0
        picked = []
        for r, i in ratio:
            if total_weight + self.weights[i] <= self.capacity:
                total_weight += self.weights[i]
                total_value += self.values[i]
                picked.append(i + 1)
        print(f"Greedy picked items: {picked}, Total value: {total_value}")

    def dp(self):
        n = len(self.weights)
        dp = [[0] * (self.capacity + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            w = self.weights[i - 1]
            v = self.values[i - 1]
            for c in range(self.capacity + 1):
                if w <= c:
                    dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)
                else:
                    dp[i][c] = dp[i - 1][c]
        # Backtrack to find picked items
        c = self.capacity
        picked = []
        for i in range(n, 0, -1):
            if dp[i][c] != dp[i - 1][c]:
                picked.append(i)
                c -= self.weights[i - 1]
        picked.reverse()
        print(f"DP picked items: {picked}, Total value: {dp[n][self.capacity]}")

knapsack = Knapsack(weights=[6, 5, 5], values=[30, 20, 20], capacity=10)
knapsack.greedy()
knapsack.dp()

ratio = [(v / w, i) for i, (v, w) in enumerate(zip(self.values, self.weights))]

Calculate value-to-weight ratio for greedy choice

ratio.sort(reverse=True)

Sort items by best ratio first

if total_weight + self.weights[i] <= self.capacity:

Check if item fits in remaining capacity

dp = [[0] * (self.capacity + 1) for _ in range(n + 1)]

Initialize DP table for subproblems

dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)

Choose max value between skipping or taking current item

if dp[i][c] != dp[i - 1][c]:

Backtrack to find which items were picked

Output

Greedy picked items: [1], Total value: 30

DP picked items: [2, 3], Total value: 40

Complexity Analysis

Time: O(n log n) for greedy due to sorting; O(n * capacity) for DP because it fills a table for all items and capacities

Space: O(n) for greedy to store ratios; O(n * capacity) for DP to store the table

vs Alternative: Greedy is faster but may miss best solution; DP is slower but guarantees optimal solution

Edge Cases

Empty list of items

Both greedy and DP return no items and zero value

DSA Python

for i in range(1, n + 1):

Capacity zero

No items can be picked, total value zero

DSA Python

if total_weight + self.weights[i] <= self.capacity:

Items with zero weight

Greedy crashes on div/0 unless handled; DP handles correctly by including them

DSA Python

dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)

When to Use This Pattern

When a problem asks for the best total value under constraints and greedy choices don't always lead to optimal, try DP; if local best choices always lead to global best, greedy works.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution
Fix: Check if problem has the greedy-choice property; if not, use DP

Mistake: Not sorting items by ratio in greedy
Fix: Always sort items by value-to-weight ratio before greedy selection

Summary

Greedy picks best immediate choice; DP tries all choices and remembers results.

Use greedy when local best choices lead to global best; use DP when problem needs exploring all options.

The key is to know if the problem has the greedy-choice property or requires overlapping subproblems solved by DP.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has optimal substructure and no overlapping subproblems

B. When the problem has overlapping subproblems and requires memoization

C. When the problem requires checking all possible combinations

D. When the problem involves sorting large datasets

Solution

1. Step 1: Understand greedy algorithm conditions

   Greedy algorithms work when choosing the best option at each step leads to a global optimum, which means the problem has optimal substructure and no overlapping subproblems.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when problems have overlapping subproblems and require storing intermediate results (memoization) to avoid repeated work.

3. Final Answer:

   When the problem has optimal substructure and no overlapping subproblems -> Option A

4. Quick Check:

   Greedy = optimal substructure + no overlap [OK]

Hint: Use greedy if no overlapping subproblems exist [OK]

Common Mistakes:

• Confusing overlapping subproblems as a greedy condition
• Thinking greedy always finds the best solution
• Using dynamic programming when greedy suffices

2. Which of the following Python code snippets correctly initializes a memoization dictionary for dynamic programming?

easy

A. memo = []

B. memo = {}

C. memo = set()

D. memo = 0

Solution

1. Step 1: Identify the correct data structure for memoization

   Memoization requires storing key-value pairs of subproblem results, so a dictionary (hash map) is appropriate.

2. Step 2: Check the options

   memo = {} initializes an empty dictionary, which is correct. Lists or sets do not store key-value pairs, and an integer cannot store multiple results.

3. Final Answer:

   memo = {} -> Option B

4. Quick Check:

   Memoization uses dictionary = {} [OK]

Hint: Use {} to store subproblem results in DP [OK]

Common Mistakes:

• Using list or set instead of dictionary for memo
• Initializing memo as a number
• Confusing data structures for memoization

3. What is the output of the following Python code that uses a greedy approach to select intervals?

intervals = [(1, 3), (2, 5), (4, 7)]
intervals.sort(key=lambda x: x[1])
selected = []
end = 0
for start, finish in intervals:
    if start >= end:
        selected.append((start, finish))
        end = finish
print(selected)

medium

A. [(1, 3), (2, 5)]

B. [(2, 5), (4, 7)]

C. [(1, 3), (4, 7)]

D. [(1, 3), (2, 5), (4, 7)]

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [(1, 3), (2, 5), (4, 7)]

2. Step 2: Select intervals greedily

   Start with end=0. (1,3) start=1 >=0, select it, end=3. Next (2,5) start=2 <3 skip. Next (4,7) start=4 >=3 select it.

3. Final Answer:

   [(1, 3), (4, 7)] -> Option C

4. Quick Check:

   Greedy interval selection = [(1, 3), (4, 7)] [OK]

Hint: Sort by finish time, pick earliest finishing intervals [OK]

Common Mistakes:

• Not sorting intervals by finish time
• Selecting overlapping intervals
• Appending intervals without condition

4. The following code attempts to solve the Fibonacci sequence using dynamic programming but has a bug. What is the error?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(5))

medium

A. Mutable default argument causes incorrect memoization across calls

B. Missing base case for n=0

C. Incorrect recursive calls fib(n-1) and fib(n-2)

D. Memo dictionary is not updated

Solution

1. Step 1: Identify the use of mutable default argument

   The function uses memo={} as a default argument, which is mutable and shared across calls, causing unexpected behavior if fib is called multiple times.

2. Step 2: Explain why this is a bug

   This can cause memo to retain values from previous calls, leading to incorrect results or memory issues.

3. Final Answer:

   Mutable default argument causes incorrect memoization across calls -> Option A

4. Quick Check:

   Mutable default dict in function = bug [OK]

Hint: Avoid mutable defaults like dict in function args [OK]

Common Mistakes:

• Ignoring mutable default argument issue
• Thinking base cases are missing
• Assuming memo is not updated

5. You want to find the minimum number of coins to make a target amount using coin denominations [1, 3, 4]. Which approach is best and why? A greedy approach picks the largest coin first. Dynamic programming tries all combinations. Which is correct?

hard

A. Neither approach works for coin change problems

B. Greedy always works because picking largest coin reduces count

C. Greedy and dynamic programming give the same result here

D. Dynamic programming is needed because greedy fails for some amounts

Solution

1. Step 1: Understand greedy approach limitation

   Greedy picks largest coin first, but for amount 6, greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins.

2. Step 2: Recognize dynamic programming advantage

   Dynamic programming tries all combinations and finds minimum coins, handling cases where greedy fails.

3. Final Answer:

   Dynamic programming is needed because greedy fails for some amounts -> Option D

4. Quick Check:

   Coin change needs DP, greedy can fail [OK]

Hint: Use DP for coin change; greedy can fail [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring counterexamples where greedy fails
• Thinking coin change is always greedy