Greedy vs DP How to Know Which to Apply in DSA Python - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Use Greedy Algorithms?

Which of the following problem characteristics best indicates that a greedy algorithm is suitable?

A The problem has optimal substructure and the greedy choice property.

B The problem has overlapping subproblems and requires memoization.

C The problem requires exploring all possible combinations to find the best solution.

D The problem solution depends on future decisions that cannot be reversed.

💡 Hint

Think about when making the best local choice leads to a global best solution.

Greedy algorithms work when the problem has the greedy choice property, meaning a local optimal choice leads to a global optimum, and optimal substructure, meaning optimal solutions to subproblems build the overall solution.

❓ Predict Output

intermediate

Output of Coin Change with Greedy Approach

What is the output of the following code that tries to make change for 30 using greedy with coins [25, 10, 5, 1]?

DSA Python

coins = [25, 10, 5, 1]
amount = 30
result = []
for coin in coins:
    while amount >= coin:
        amount -= coin
        result.append(coin)
print(result)

A [10, 10, 10]

B [25, 5]

C [25, 1, 1, 1, 1, 1]

D [5, 5, 5, 5, 5, 5]

💡 Hint

Check how the greedy approach picks the largest coin first and subtracts until it can't.

The greedy approach picks 25 first, then 5 to make 30. It does not try to use three 10s because 25 is larger and chosen first.

❓ Predict Output

advanced

Dynamic Programming Table for Fibonacci

What is the content of the dp array after running this code to compute fib(5)?

DSA Python

dp = [0, 1] + [0]*4
for i in range(2, 6):
    dp[i] = dp[i-1] + dp[i-2]
print(dp)

A [0, 1, 1, 3, 4, 7]

B [0, 1, 2, 3, 5, 8]

C [1, 1, 2, 3, 5, 8]

D [0, 1, 1, 2, 3, 5]

💡 Hint

Remember Fibonacci starts with 0,1 and each next number is sum of previous two.

The dp array stores Fibonacci numbers from 0 to 5: 0,1,1,2,3,5.

🧠 Conceptual

advanced

Why Dynamic Programming Over Greedy?

Why would you choose dynamic programming instead of a greedy algorithm for some problems?

A Because greedy algorithms require more memory than dynamic programming.

B Because dynamic programming is faster than greedy in all cases.

C Because the problem has overlapping subproblems and no greedy choice property.

D Because greedy algorithms always give the wrong answer.

💡 Hint

Think about when greedy choices do not lead to the best overall solution.

Dynamic programming is used when problems have overlapping subproblems and optimal substructure but lack the greedy choice property, so greedy algorithms may fail.

🚀 Application

expert

Choosing Algorithm for Job Scheduling with Deadlines

You have jobs with deadlines and profits. You want to maximize profit by scheduling jobs before their deadlines. Which approach is best?

A Use a greedy algorithm that schedules jobs in order of highest profit first, placing them in the latest available slot before deadline.

B Use dynamic programming to try all job combinations and pick the best profit sum.

C Use a divide and conquer approach to split jobs and merge schedules.

D Use a simple loop to schedule jobs in the order they appear without sorting.

💡 Hint

Think about how to pick jobs to maximize profit without conflicts.

The job scheduling with deadlines problem is classically solved by a greedy approach that sorts jobs by profit and schedules each in the latest free slot before its deadline.

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