DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci with Memoization

What is the output of the following Python code that uses recursion with memoization to compute Fibonacci numbers?

DSA Python

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

print(fib(6))

A 8

B 13

C 5

D 21

💡 Hint

Remember Fibonacci sequence starts 0,1,1,2,3,5,8,13...

The function computes Fibonacci numbers using recursion and memoization. fib(6) returns the 6th Fibonacci number which is 8.

🧠 Conceptual

intermediate

Choosing Greedy vs DP for Coin Change Problem

Which statement correctly describes when a greedy algorithm works for the coin change problem?

A Greedy always works for any coin denominations.

B Greedy never works; dynamic programming is always needed.

C Greedy works only if the target amount is less than the largest coin.

D Greedy works only if coin denominations are canonical (like 1, 5, 10, 25).

💡 Hint

Think about US coin denominations and why greedy works there.

Greedy works for coin change only if the coin denominations are canonical, meaning the greedy choice leads to an optimal solution. For example, US coins (1,5,10,25) satisfy this.

❓ Predict Output

advanced

Output of DP Longest Increasing Subsequence Length

What is the output of the following Python code that finds the length of the longest increasing subsequence using dynamic programming?

DSA Python

def length_of_LIS(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(length_of_LIS([10,9,2,5,3,7,101,18]))

A 3

B 5

C 4

D 6

💡 Hint

Find the longest increasing subsequence in the list.

The longest increasing subsequence is [2,3,7,101] which has length 4.

❓ Predict Output

advanced

Output of Greedy Interval Scheduling Algorithm

What is the output (number of intervals selected) of the following greedy algorithm that selects the maximum number of non-overlapping intervals?

DSA Python

intervals = [(1,3), (2,5), (4,7), (6,9), (8,10)]
intervals.sort(key=lambda x: x[1])
count = 0
end = float('-inf')
for interval in intervals:
    if interval[0] >= end:
        count += 1
        end = interval[1]
print(count)

A 4

B 3

C 2

D 5

💡 Hint

Sort intervals by finish time and pick compatible ones.

The greedy algorithm picks intervals (1,3), (4,7), and (8,10) for a total of 3 intervals.

🧠 Conceptual

expert

Why DP is Needed Over Greedy in Weighted Interval Scheduling

Why does the weighted interval scheduling problem require dynamic programming instead of a greedy approach?

A Because intervals can overlap and weights require considering multiple combinations.

B Because greedy algorithms cannot sort intervals by finish time.

C Because dynamic programming is always faster than greedy.

D Because weights are always negative and greedy fails.

💡 Hint

Think about why just picking earliest finishing intervals might not maximize total weight.

Weighted interval scheduling requires considering overlapping intervals and their weights, so we must consider multiple combinations to find the maximum total weight, which greedy cannot do.

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