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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci with Memoization

What is the output of the following C code that calculates the 5th Fibonacci number using recursion with memoization?

DSA C

#include <stdio.h>

int fib(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

int main() {
    int n = 5;
    int memo[6];
    for (int i = 0; i <= n; i++) memo[i] = -1;
    int result = fib(n, memo);
    printf("%d\n", result);
    return 0;
}

A 3

B 8

C 5

D 13

💡 Hint

Remember Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

The 5th Fibonacci number (0-based index) is 5. The code uses memoization to avoid repeated calculations.

🧠 Conceptual

intermediate

Choosing Greedy vs Dynamic Programming

Which problem characteristic best indicates that a greedy algorithm will NOT always produce the optimal solution, and dynamic programming should be considered instead?

A The problem has overlapping subproblems and optimal substructure

B The problem can be solved by making locally optimal choices that lead to a global optimum

C The problem has no overlapping subproblems and no optimal substructure

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

💡 Hint

Think about when greedy fails and DP helps.

When a problem has overlapping subproblems and optimal substructure, greedy may fail because local choices don't guarantee global optimum. DP handles this by exploring all subproblems.

🔧 Debug

advanced

Why Does This Greedy Coin Change Fail?

Consider the coin denominations {1, 3, 4} and the amount 6. The greedy algorithm picks the largest coin possible at each step. What is the output of the code below, and why does it fail to find the minimum number of coins?

DSA C

#include <stdio.h>

int minCoins(int amount) {
    int coins[] = {4, 3, 1};
    int count = 0;
    int i = 0;
    while (amount > 0) {
        if (coins[i] <= amount) {
            amount -= coins[i];
            count++;
        } else {
            i++;
        }
    }
    return count;
}

int main() {
    int amount = 6;
    printf("%d\n", minCoins(amount));
    return 0;
}

A 2 (coins used: 3 + 3), greedy works correctly here

B 3 (coins used: 4 + 1 + 1), greedy fails because it doesn't find the minimum 2 coins (3 + 3)

C 4 (coins used: 1 + 1 + 1 + 3), greedy fails due to wrong coin order

D 1 (coin used: 6), greedy fails because coin 6 doesn't exist

💡 Hint

Try to find the minimum coins manually and compare with greedy output.

Greedy picks 4 first, then two 1s, total 3 coins. But minimum coins are two 3s. Greedy fails because local largest coin choice is not optimal here.

❓ Predict Output

advanced

Dynamic Programming Table for 0/1 Knapsack

What is the value stored in dp[3][5] after running the 0/1 Knapsack dynamic programming code below? Items have weights {1, 3, 4} and values {15, 20, 30}, capacity is 5.

DSA C

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int main() {
    int weights[] = {1, 3, 4};
    int values[] = {15, 20, 30};
    int n = 3, W = 5;
    int dp[4][6] = {0};

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    printf("%d\n", dp[3][5]);
    return 0;
}

A 45

B 35

C 65

D 50

💡 Hint

Try to fill the dp table step by step for capacity 5.

The maximum value for capacity 5 is 45, obtained by choosing items with weights 1 and 4 (values 15 + 30).

🧠 Conceptual

expert

When to Prefer Recursion with Memoization Over Iterative DP

In which scenario is recursion with memoization preferred over iterative dynamic programming?

A When the problem size is very large and iterative solutions are faster

B When the problem requires filling a complete DP table for all subproblems

C When the problem has no overlapping subproblems

D When the problem has a complex state space and not all states need to be computed

💡 Hint

Think about when memoization avoids unnecessary computations.

Memoization computes only needed states on demand, saving time and memory when many states are not required. Iterative DP computes all states regardless.

Practice

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

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

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

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option A

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 subproblems overlap
• Using simple recursion without memoization causing slow code
• Confusing optimal substructure with greedy choice property

2. Which of the following is the correct syntax to implement memoization in C for a recursive Fibonacci function?

easy

A. Use a global array to store results and check before recursive calls

B. Use a local variable inside the function to store results

C. Use a static variable without initialization inside the function

D. Use a pointer without allocating memory for memoization

Solution

1. Step 1: Understand memoization storage

   Memoization requires storing results outside the recursive calls to reuse them. A global or static array is suitable.

2. Step 2: Check options for correct usage

   Only a global array checked before recursion ensures stored results are reused properly. Local variables reset each call, static without init may cause errors, pointers need allocation.

3. Final Answer:

   Use a global array to store results and check before recursive calls -> Option A

4. Quick Check:

   Memoization needs persistent storage = global array [OK]

Hint: Memoize with global/static array checked before recursion [OK]

Common Mistakes:

• Using local variables that reset each call
• Not initializing static variables properly
• Using pointers without memory allocation

3. What will be the output of the following C code snippet implementing a greedy approach for coin change?

int coins[] = {25, 10, 5, 1};
int amount = 30;
int count = 0;
for (int i = 0; i < 4; i++) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("%d\n", count);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Trace the greedy coin selection

   Start with 30 amount. Use 25 coin once (30-25=5), count=1. Then 10 coin can't be used (5<10). Use 5 coin once (5-5=0), count=2.

2. Step 2: Count total coins used

   Coins used: 25 (1), 5 (1), total count = 2 coins. The code increments count inside while loop, so count=2.

3. Step 3: Check for remaining coins

   Amount is now 0, so no more coins used.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Greedy coin count for 30 = 2 coins [OK]

Hint: Subtract largest coin repeatedly until amount zero [OK]

Common Mistakes:

• Counting coins incorrectly by missing loops
• Assuming greedy always gives minimum coins
• Confusing coin values and counts

4. Identify the error in this recursive function for factorial and suggest the fix:

int factorial(int n) {
    if (n == 0) return 0;
    return n * factorial(n - 1);
}

medium

A. Recursive call should be factorial(n + 1)

B. Function should return void

C. Base case should return 1 instead of 0

D. No error, code is correct

Solution

1. Step 1: Analyze base case correctness

   Factorial of 0 is 1, but code returns 0, which will cause all results to be zero.

2. Step 2: Suggest correct base case

   Change base case to return 1 when n == 0 to correctly end recursion and compute factorial.

3. Final Answer:

   Base case should return 1 instead of 0 -> Option C

4. Quick Check:

   Factorial(0) = 1 base case [OK]

Hint: Factorial base case returns 1, not 0 [OK]

Common Mistakes:

• Returning 0 in base case causing zero product
• Changing recursion direction incorrectly
• Ignoring base case leading to infinite recursion

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

hard

A. Brute force, to try all combinations without optimization

B. Recursion without memoization, to explore all possibilities

C. Greedy, because always picking largest coin works

D. Dynamic Programming, to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   Minimum coins for amount with coins {1,3,4} needs checking all combinations to find optimal solution.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins. Recursion without memoization is slow. Dynamic Programming stores results of smaller amounts to build 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 when greedy fails to find minimum coins [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Using recursion without memo causing slow code
• Ignoring overlapping subproblems in coin change