Greedy vs DP How to Know Which to Apply in DSA Python - Build Both Approaches

Greedy vs Dynamic Programming: How to Know Which to Apply

📖 Scenario: Imagine you are organizing a small event and need to decide how to allocate your budget to buy snacks. You want to maximize the number of snacks you can buy without exceeding your budget. Sometimes, a simple quick choice works best, but other times, you need to carefully consider all options to get the best result.

🎯 Goal: You will learn how to decide when to use a simple step-by-step choice method (Greedy) and when to use a careful planning method (Dynamic Programming) by solving a snack buying problem.

📋 What You'll Learn

Create a list of snack prices

Set a budget limit

Use a greedy approach to pick snacks

Use a dynamic programming approach to pick snacks

Compare the results of both methods

💡 Why This Matters

🌍 Real World

Choosing items to buy within a budget is a common problem in shopping, event planning, and resource allocation.

💼 Career

Understanding when to use greedy or dynamic programming helps in software development, especially in optimization and decision-making tasks.

1

Create the snack prices list

Create a list called snack_prices with these exact values: [2, 3, 4, 5]

DSA Python

# Create the snack_prices list with values [2, 3, 4, 5]
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Set the budget limit

Create a variable called budget and set it to 7

DSA Python

snack_prices = [2, 3, 4, 5]
# Create a variable called budget and set it to 7
# Your code here

Hint

Use the equals sign to assign the number 7 to the variable budget.

3

Apply the greedy approach to pick snacks

Write code to pick snacks using a greedy method: create a list called greedy_selection, start with total_cost = 0, then use a for loop with variable price over snack_prices sorted in ascending order. Inside the loop, if total_cost + price <= budget, add price to greedy_selection and update total_cost by adding price

DSA Python

snack_prices = [2, 3, 4, 5]
budget = 7
# Use a greedy approach to pick snacks within budget
# Your code here

Hint

Sort the snack prices from smallest to largest and pick snacks while you can afford them.

4

Use dynamic programming to find the best snack combination and print results

Write code to find the best snack combination using dynamic programming: create a list dp of length budget + 1 with empty lists. Use a for loop with variable price over snack_prices. Inside it, use a for loop with variable curr_budget from budget down to price. If len(dp[curr_budget - price]) + 1 ≥ len(dp[curr_budget]), update dp[curr_budget] to dp[curr_budget - price] + [price]. After loops, assign dp[budget] to dp_selection. Then print greedy_selection and dp_selection as shown.

DSA Python

snack_prices = [2, 3, 4, 5]
budget = 7
greedy_selection = []
total_cost = 0
for price in sorted(snack_prices):
    if total_cost + price <= budget:
        greedy_selection.append(price)
        total_cost += price

# Use dynamic programming to find best snack combination
# Print both greedy_selection and dp_selection
# Your code here

Hint

Dynamic programming tries all combinations to find the largest number of snacks within budget.

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