DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are helping a small delivery company decide the best way to deliver packages to customers. Each package has a value and a weight. The company wants to maximize the total value of packages delivered without exceeding the truck's weight limit.You will explore three ways to solve this problem: simple recursion, greedy choice, and dynamic programming. This will help you understand when each method works best.

🎯 Goal: Build three solutions to the package delivery problem using recursion, greedy, and dynamic programming. Compare their results to see which method gives the best total value without exceeding the weight limit.

📋 What You'll Learn

Create a list of packages with exact weights and values

Set a weight limit for the delivery truck

Write a recursive function to find the best value

Write a greedy function to pick packages by value-to-weight ratio

Write a dynamic programming function to find the best value efficiently

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Delivery companies and logistics planners often need to decide which packages to load to maximize value without exceeding weight limits.

💼 Career

Understanding recursion, greedy algorithms, and dynamic programming helps software engineers solve optimization problems efficiently in many industries.

1

Create the package list

Create a list called packages with these exact tuples representing (weight, value): (2, 3), (3, 4), (4, 5), (5, 8).

DSA Python

# Your code here

Hint

Use a list of tuples where each tuple has weight first, then value.

2

Set the weight limit

Create a variable called weight_limit and set it to 8.

DSA Python

packages = [(2, 3), (3, 4), (4, 5), (5, 8)]
# Your code here

Hint

This is the maximum weight the truck can carry.

3

Write the recursive solution

Write a recursive function called knapsack_recursive that takes index and remaining_weight as parameters and returns the maximum value. Use the packages list and weight_limit variable. The function should check if the current package can be included or excluded and return the best value.

DSA Python

packages = [(2, 3), (3, 4), (4, 5), (5, 8)]
weight_limit = 8

def knapsack_recursive(index, remaining_weight):
    # Your code here

Hint

Use base case when index reaches end or no weight left. Then choose max of including or excluding current package.

4

Print the recursive solution result

Print the result of calling knapsack_recursive(0, weight_limit).

DSA Python

packages = [(2, 3), (3, 4), (4, 5), (5, 8)]
weight_limit = 8

def knapsack_recursive(index, remaining_weight):
    if index == len(packages) or remaining_weight == 0:
        return 0
    weight, value = packages[index]
    if weight > remaining_weight:
        return knapsack_recursive(index + 1, remaining_weight)
    else:
        include = value + knapsack_recursive(index + 1, remaining_weight - weight)
        exclude = knapsack_recursive(index + 1, remaining_weight)
        return max(include, exclude)

print(knapsack_recursive(0, weight_limit))  # Your code here

Hint

The recursive solution should print the maximum value 12.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Brute Force

B. Greedy Algorithm

C. Dynamic Programming

D. Simple Recursion without memoization

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems mean the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller parts.

2. Step 2: Match approach to properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

3. Final Answer:

   Dynamic Programming -> Option C

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when problem needs global optimization
• Using simple recursion causing repeated calculations
• Confusing brute force with efficient methods

2. Which of the following Python function definitions correctly implements a recursive Fibonacci function?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): for i in range(n): return fib(i-1) + fib(i-2)

C. def fib(n): while n > 1: n -= 1 return n

D. def fib(n): return n + fib(n-1)

Solution

1. Step 1: Check base case and recursion

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) correctly returns n if n <= 1, else calls fib(n-1) + fib(n-2).

2. Step 2: Verify other options

   Options B, C, and D have syntax or logic errors: B uses for loop wrongly, C uses while without recursion, D causes infinite recursion.

3. Final Answer:

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) -> Option A

4. Quick Check:

   Correct recursive base and calls = def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) [OK]

Hint: Base case + two recursive calls = correct Fibonacci recursion [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion incorrectly
• Wrong return statements inside recursion

3. What is the output of the following code?

def max_sum(arr, n):
    if n == 0:
        return 0
    elif n == 1:
        return arr[0]
    else:
        return max(max_sum(arr, n-1), max_sum(arr, n-2) + arr[n-1])

print(max_sum([3, 2, 7, 10], 4))

medium

A. 13

B. 17

C. 20

D. 10

Solution

1. Step 1: Understand function logic

   max_sum returns max sum of non-adjacent elements from first n elements.

2. Step 2: Trace calls for n=4

   max_sum(arr,4) = max(max_sum(arr,3), max_sum(arr,2) + arr[3]) max_sum(arr,3) = max(max_sum(arr,2), max_sum(arr,1) + arr[2]) max_sum(arr,2) = max(max_sum(arr,1), max_sum(arr,0) + arr[1]) Calculate bottom-up: max_sum(arr,0)=0 max_sum(arr,1)=3 max_sum(arr,2)=max(3,0+2)=3 max_sum(arr,3)=max(3,3+7)=10 max_sum(arr,4)=max(10,3+10)=13

3. Final Answer:

   13 -> Option A

4. Quick Check:

   Max sum non-adjacent = 13 [OK]

Hint: Trace recursion bottom-up for max sum non-adjacent [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Confusing indices in recursion
• Ignoring base cases

4. The following code tries to solve the coin change problem using recursion but has an error. What is the error?

def coin_change(coins, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    count = 0
    for coin in coins:
        count += coin_change(coins, amount - coin)
    return count

print(coin_change([1, 2], 3))

medium

A. It does not handle negative amounts correctly

B. It counts duplicate combinations multiple times

C. It misses base case for amount == 1

D. It uses iteration instead of recursion

Solution

1. Step 1: Analyze recursion logic

   The function counts ways to make amount by subtracting coins recursively.

2. Step 2: Identify counting duplicates

   Because it tries all coins at each step without order control, it counts same combinations in different orders multiple times.

3. Final Answer:

   It counts duplicate combinations multiple times -> Option B

4. Quick Check:

   Duplicates counted due to unordered recursion [OK]

Hint: Unordered recursion counts duplicates; use order or DP to fix [OK]

Common Mistakes:

• Assuming base cases are missing
• Confusing negative amount handling
• Thinking iteration replaces recursion

5. You want to find the minimum number of coins needed to make a given amount using coin denominations [1, 3, 4]. Which approach is best and why?

hard

A. Brute force trying all combinations without optimization

B. Simple recursion without memoization for clarity

C. Greedy algorithm because always picking largest coin works

D. Dynamic Programming to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   We want minimum coins to make amount, which requires checking all combinations to find optimal.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins (e.g., amount=6, greedy picks 4+1+1=3 coins, but 3+3=2 coins is better). Simple recursion repeats subproblems causing inefficiency. DP stores results to avoid repeated work and finds optimal solution efficiently.

3. Final Answer:

   Dynamic Programming to store and reuse subproblem results -> Option D

4. Quick Check:

   Minimum coins with overlapping subproblems = DP [OK]

Hint: Use DP for minimum coins; greedy can fail with some denominations [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring efficiency of memoization
• Using brute force causing timeouts