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 Fibonacci numbers using recursion with memoization?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    static int Fib(int n) {
        if (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        int result = Fib(n - 1) + Fib(n - 2);
        memo[n] = result;
        return result;
    }

    static void Main() {
        Console.WriteLine(Fib(6));
    }
}

A 21

B 15

C 8

D 13

💡 Hint

Recall the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13...

The Fibonacci sequence starts with 0 and 1. Fib(6) = Fib(5) + Fib(4) = 5 + 3 = 8.

🧠 Conceptual

intermediate

Choosing Greedy vs Dynamic Programming

Which problem characteristic best indicates that a greedy algorithm is suitable instead of dynamic programming?

A The problem has the greedy-choice property where local optimum choices lead to global optimum.

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

C The problem involves complex state transitions and multiple constraints.

D The problem has overlapping subproblems and optimal substructure.

💡 Hint

Greedy algorithms work well when making the best local choice leads to the best overall solution.

Greedy algorithms are suitable when the problem has the greedy-choice property, meaning local optimal choices lead to a global optimum without needing to explore all possibilities.

❓ Predict Output

advanced

Output of Recursive vs DP Coin Change Count

What is the output of the following C# code that counts ways to make change using recursion and dynamic programming?

DSA C#

using System;

class Program {
    static int CountWaysRecursive(int[] coins, int n, int amount) {
        if (amount == 0) return 1;
        if (amount < 0 || n <= 0) return 0;
        return CountWaysRecursive(coins, n - 1, amount) + CountWaysRecursive(coins, n, amount - coins[n - 1]);
    }

    static int CountWaysDP(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        foreach (var coin in coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    static void Main() {
        int[] coins = {1, 2, 3};
        int amount = 4;
        Console.WriteLine(CountWaysRecursive(coins, coins.Length, amount));
        Console.WriteLine(CountWaysDP(coins, amount));
    }
}

A 6\n6

B 7\n7

C 5\n5

D 4\n4

💡 Hint

Count the number of ways to make 4 using coins 1, 2, 3.

Both recursive and DP methods count 4 ways to make amount 4 with coins 1, 2, 3.

🧠 Conceptual

advanced

Why DP is Preferred Over Recursion Alone

Why is dynamic programming often preferred over plain recursion for problems with overlapping subproblems?

A DP uses memoization or tabulation to avoid repeated calculations, improving efficiency.

B Recursion always uses more memory than DP.

C DP algorithms are easier to write than recursive ones.

D Recursion cannot solve problems with optimal substructure.

💡 Hint

Think about how DP stores results to save time.

DP stores results of subproblems to avoid recalculating them, making it faster than plain recursion which may recompute the same results multiple times.

🚀 Application

expert

Choosing the Right Tool for Job Scheduling Problem

You have a set of jobs with start and end times and profits. You want to schedule jobs to maximize total profit without overlapping. Which approach is best suited?

A Use a greedy algorithm that always picks the job with the highest profit first.

B Use dynamic programming with sorting jobs by end time and storing max profit up to each job.

C Use recursion without memoization to explore all job combinations.

D Use a simple loop to pick jobs randomly and sum profits.

💡 Hint

Consider overlapping intervals and optimal substructure.

The weighted job scheduling problem is best solved by dynamic programming after sorting jobs by end time, using stored results to find max profit without overlaps.

Practice

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

easy

A. Simple Recursion

B. Dynamic Programming

C. Greedy Algorithm

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 recomputation, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option B

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
• Confusing optimal substructure with greedy choice

2. Which of the following C# code snippets correctly implements a greedy approach to find the maximum number of activities that don't overlap given start and end times arrays (assuming sorted by end time)?

easy

A. int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count);

B. int count = 0; for (int i = 0; i < start.Length; i++) { if (start[i] > end[i]) count++; } Console.WriteLine(count);

C. int count = 1; for (int i = 1; i < start.Length; i++) { if (end[i] >= start[i-1]) count++; } Console.WriteLine(count);

D. int count = 0; foreach (var s in start) { count += s; } Console.WriteLine(count);

Solution

1. Step 1: Understand greedy activity selection logic

   We select the first activity, then pick next activities starting after the last selected activity ends.

2. Step 2: Check code correctness

   int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); initializes count to 1, tracks lastEnd, and increments count only if start[i] >= lastEnd, updating lastEnd. This matches greedy logic.

3. Final Answer:

   the code that tracks lastEnd -> Option A

4. Quick Check:

   Greedy activity selection code = int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); [OK]

Hint: Pick next activity starting after last selected ends [OK]

Common Mistakes:

• Not sorting activities by end time before selection
• Comparing start[i] with wrong end time
• Counting activities incorrectly

3. What is the output of the following C# code that uses recursion to calculate Fibonacci numbers without memoization?

int Fib(int n) { if (n <= 1) return n; return Fib(n - 1) + Fib(n - 2); } Console.WriteLine(Fib(5));

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace recursive calls for Fib(5)

   Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0); Fib(1)=1, Fib(0)=0.

2. Step 2: Calculate values bottom-up

   Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) = 5 by definition [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Miscomputing recursive sums
• Assuming memoization changes output

4. The following C# code attempts to solve the coin change problem using recursion but has a bug. What is the bug?

int CoinChange(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; int min = int.MaxValue; foreach (int coin in coins) { int res = CoinChange(coins, amount - coin); if (res >= 0 && res < min) min = 1 + res; } return min == int.MaxValue ? -1 : min; }

medium

A. No memoization causing repeated calculations

B. Incorrect base case for amount == 0

C. Returning -1 instead of 0 for amount < 0

D. Using foreach instead of for loop

Solution

1. Step 1: Analyze recursion and base cases

   Base cases are correct: 0 returns 0, negative returns -1. The recursion tries all coins.

2. Step 2: Identify missing optimization

   Without memoization, the function recalculates subproblems many times, causing inefficiency and possible stack overflow.

3. Final Answer:

   No memoization causing repeated calculations -> Option A

4. Quick Check:

   Missing memoization = No memoization causing repeated calculations [OK]

Hint: Add memo dictionary to avoid repeated calls [OK]

Common Mistakes:

• Thinking base cases are wrong
• Believing loop type causes bug
• Ignoring performance issues

5. You want to find the minimum number of coins needed to make a given amount using coins of different denominations. Which approach is best and why?

hard

A. Greedy algorithm may fail for some coin sets

B. Simple iteration misses subproblem reuse

C. Recursion without memoization is inefficient

D. Dynamic programming ensures optimal solution efficiently

Solution

1. Step 1: Evaluate greedy approach limitations

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it can fail to find minimum coins.

2. Step 2: Consider recursion and iteration drawbacks

   Recursion without memoization repeats work; simple iteration without storing results misses subproblem reuse.

3. Step 3: Understand dynamic programming benefits

   DP with bottom-up tabulation stores minimum coins for all amounts up to target, guaranteeing optimal and efficient solution.

4. Final Answer:

   Dynamic programming ensures optimal solution efficiently -> Option D

5. Quick Check:

   Minimum coins problem = DP bottom-up [OK]

Hint: Use DP tabulation for guaranteed minimum coins [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring performance of recursion
• Not storing intermediate results