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

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are helping a small shop owner decide how to pack items into a box to maximize value without exceeding the box's weight limit. You will explore three ways to solve this problem: simple recursion, dynamic programming, and a greedy approach.

🎯 Goal: You will create a list of items with weights and values, set a weight limit, then write code to find the best total value using recursion, dynamic programming, and greedy methods. Finally, you will print the results to compare.

📋 What You'll Learn

Create a list of items with exact weights and values

Set an integer variable for the weight limit

Write a recursive function to find max value without exceeding weight limit

Write a dynamic programming function to find max value without exceeding weight limit

Write a greedy function to select items based on value-to-weight ratio

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Packing items efficiently is important in shipping, travel, and storage to save space and cost.

💼 Career

Understanding recursion, dynamic programming, and greedy algorithms helps solve optimization problems in software development and data science.

1

Create the list of items

Create a list called items containing these exact tuples of (weight, value): (2, 3), (3, 4), (4, 5), (5, 8).

DSA C#

# Create the list of items as tuples (weight, value)
# Your code here

Hint

Use List<(int, int)> and add the exact tuples inside curly braces.

2

Set the weight limit

Add an integer variable called weightLimit and set it to 8.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List items = new List
        {
            (2, 3),
            (3, 4),
            (4, 5),
            (5, 8)
        };
        // Set the weight limit
        // Your code here
    }
}

Hint

Use int weightLimit = 8; inside the Main method.

3

Write the recursive function

Add a static recursive method called MaxValueRecursive with parameters List<(int weight, int value)> items, int n, and int remainingWeight. It returns the maximum value that fits in the remaining weight. Use recursion to include or exclude the current item at index n - 1. Return 0 if n is 0 or remainingWeight is 0.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static int MaxValueRecursive(List items, int n, int remainingWeight)
    {
        // Your code here
    }

    static void Main()
    {
        List items = new List
        {
            (2, 3),
            (3, 4),
            (4, 5),
            (5, 8)
        };
        int weightLimit = 8;
    }
}

Hint

Use base case for n == 0 or remainingWeight == 0. Then decide to include or exclude the current item recursively.

4

Print the recursive result

Inside Main, call MaxValueRecursive(items, items.Count, weightLimit) and print the result with Console.WriteLine.

DSA C#

Hint

Call MaxValueRecursive(items, items.Count, weightLimit) and print the result.

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