Greedy vs DP How to Know Which to Apply in DSA Python - Visual Comparison

Concept Flow - Greedy vs DP How to Know Which to Apply

Start Problem

↓

Check if problem has optimal substructure?

Yes↓

Check if problem has overlapping subproblems?

↓

Use DP

↓

Build solution with memo/table

↓

Done

Start by checking if the problem can be broken into smaller problems (optimal substructure). Then check if these smaller problems overlap. If yes, use DP; if no, use Greedy.

Execution Sample

DSA Python

def choose_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

This code tries to make change using the largest coins first (greedy approach).

Execution Table

Step	Operation	Amount Remaining	Coins Used	Visual State
1	Sort coins descending	30	[]	[25, 10, 5, 1]
2	Use coin 25	30	[]	Start with amount=30
3	Subtract 25	5	[25]	30 - 25 = 5
4	Use coin 25 again?	5	[25]	5 < 25, skip coin 25
5	Use coin 10	5	[25]	5 < 10, skip coin 10
6	Use coin 5	5	[25]	5 >= 5, subtract 5
7	Subtract 5	0	[25, 5]	5 - 5 = 0
8	Use coin 5 again?	0	[25, 5]	0 < 5, skip coin 5
9	Use coin 1	0	[25, 5]	0 < 1, skip coin 1
10	Return count	0	[25, 5]	Coins used: 2

💡 Amount reduced to 0, solution found using greedy approach.

Variable Tracker

Variable	Start	After Step 3	After Step 7	Final
amount	30	5	0	0
coins_used_count	0	1	2	2
coins_list	[25, 10, 5, 1]	[25, 10, 5, 1]	[25, 10, 5, 1]	[25, 10, 5, 1]

Key Moments - 3 Insights

Why do we check if the problem has overlapping subproblems before choosing DP?

Because DP saves work by reusing solutions to overlapping subproblems. If subproblems don't overlap, DP is not needed. See execution flow where overlapping subproblems lead to DP choice.

Why does greedy sometimes fail even if the problem has optimal substructure?

Greedy picks the best option locally without considering future choices. If future choices affect the result, greedy can fail. This is why checking overlapping subproblems is important.

How does the greedy example decide which coin to use first?

It sorts coins descending and always picks the largest coin possible first, as shown in the execution table steps 2-3.

Visual Quiz - 3 Questions

Look at the execution table, what is the amount remaining after step 3?

A 0

B 25

C 5

D 30

💡 Hint

Check the 'Amount Remaining' column at step 3 in the execution table.

At which step does the amount become zero?

A Step 7

B Step 9

C Step 10

D Step 5

💡 Hint

Look for the first step where 'Amount Remaining' is 0 in the execution table.

If the coins were [10, 6, 1] instead of [25, 10, 5, 1], which approach is more likely needed?

A Greedy

B Dynamic Programming

C Neither

D Both equally

💡 Hint

Refer to concept flow: overlapping subproblems with these coins require DP, not greedy.

Concept Snapshot

Greedy vs DP Decision:
- Check if problem has optimal substructure.
- If yes, check for overlapping subproblems.
- Overlapping subproblems → Use DP (store and reuse results).
- No overlap → Use Greedy (choose best local option).
- Greedy is simpler but can fail if future choices matter.
- DP is more powerful but uses more memory/time.

Full Transcript

To decide between Greedy and Dynamic Programming (DP), first check if the problem can be broken into smaller parts that build the final answer (optimal substructure). Then see if these smaller parts overlap, meaning the same subproblems repeat. If they do, DP is best because it saves work by remembering answers. If not, Greedy works by picking the best choice at each step without worrying about the future. For example, making change with coins sorted largest to smallest is greedy and works if coin denominations are standard. But if coins are tricky, DP is needed. The execution table shows how greedy picks coins step-by-step until the amount is zero. Variables track the amount left and coins used. Key moments explain why overlapping subproblems matter and why greedy can fail. The quiz tests understanding of these steps and when to use each approach.

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