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.