Greedy vs DP How to Know Which to Apply in DSA C# - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Choose Greedy Over Dynamic Programming?

Which condition best indicates that a greedy algorithm is the right choice instead of dynamic programming?

A The problem requires exploring all possible solutions to find the best one.

B The problem has an optimal substructure and overlapping subproblems.

C The problem has an optimal substructure and the greedy choice property.

D The problem has no clear optimal substructure.

💡 Hint

Think about when making the best local choice leads to a global best solution.

Greedy algorithms work when the problem has the greedy choice property, meaning a local optimal choice leads to a global optimum. Dynamic programming is needed when overlapping subproblems exist but greedy choice property does not hold.

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following C# code that uses a greedy approach to make change?

DSA C#

int[] coins = {25, 10, 5, 1};
int amount = 37;
List<int> result = new List<int>();
foreach (int coin in coins) {
    while (amount >= coin) {
        amount -= coin;
        result.Add(coin);
    }
}
Console.WriteLine(string.Join(",", result));

A "25,10,1,1"

B "25,10,5,1"

C "25,10,1,1,1"

D "25,10,5,5"

💡 Hint

Count how many coins are needed to sum up to 37 using the largest coins first.

The greedy algorithm picks 25 once, then 10 once, then two 1-cent coins to make 37 cents total.

🔧 Debug

advanced

Why Does This Greedy Algorithm Fail for Some Inputs?

Consider the following code that tries to find the minimum number of coins for amount 6 using coins {1,3,4} greedily. What is the output and why is it incorrect?

DSA C#

int[] coins = {4, 3, 1};
int amount = 6;
List<int> result = new List<int>();
foreach (int coin in coins) {
    while (amount >= coin) {
        amount -= coin;
        result.Add(coin);
    }
}
Console.WriteLine(string.Join(",", result));

A "4,1,1" - Incorrect because greedy picks largest coin first but misses better combo.

B Runtime error due to infinite loop.

C "1,1,1,1,1,1" - Greedy picks smallest coin only.

D "3,3" - Correct minimum coins for 6.

💡 Hint

Check how the greedy picks coins and if it finds the minimum number.

The greedy picks 4 first, then two 1s, totaling 3 coins. But the optimal solution is two 3s (2 coins). Greedy fails because the greedy choice property does not hold here.

❓ Predict Output

advanced

Dynamic Programming Table Value After Execution

Given the following C# code for the classic Fibonacci sequence using dynamic programming, what is the value of dp[5] after execution?

DSA C#

int n = 7;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
Console.WriteLine(dp[5]);

A 8

B 3

C 13

D 5

💡 Hint

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

dp[5] corresponds to the 5th Fibonacci number which is 5.

🧠 Conceptual

expert

Identifying Overlapping Subproblems in DP

Which of the following problem characteristics best indicates that dynamic programming is needed instead of a greedy approach?

A The problem can be solved by making a sequence of locally optimal choices.

B The problem has overlapping subproblems and optimal substructure but no greedy choice property.

C The problem requires sorting input before processing.

D The problem has no repeated subproblems and no optimal substructure.

💡 Hint

Think about when you must remember results of subproblems to avoid repeated work.

Dynamic programming is used when the problem has overlapping subproblems and optimal substructure but does not satisfy the greedy choice property, so greedy algorithms fail.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has the greedy choice property and optimal substructure

B. When the problem requires checking all possible solutions

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem is about sorting large datasets

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Check optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option A

4. Quick Check:

   Greedy choice + optimal substructure = Greedy algorithm [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Thinking sorting problems always need DP

2. Which of the following C# code snippets correctly initializes a DP array for a problem with 5 states?

easy

A. int dp = new int[5];

B. int[] dp = new int[5];

C. int[] dp = int[5];

D. int dp[] = new int(5);

Solution

1. Step 1: Check correct array declaration syntax in C#

   Arrays are declared with type[], variable = new type[size]; so int[] dp = new int[5]; is correct.

2. Step 2: Identify errors in other options

   int dp = new int[5]; misses [] for array type, C uses wrong syntax, D uses parentheses instead of brackets.

3. Final Answer:

   int[] dp = new int[5]; -> Option B

4. Quick Check:

   C# array syntax = type[] var = new type[size]; [OK]

Hint: Remember C# arrays use [] and new keyword [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using parentheses instead of brackets for arrays
• Confusing array initialization syntax

3. Consider the following C# code for a problem that can be solved by greedy or DP. What is the output?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace the greedy coin counting

   Start with coins = {1,3,4}, amount = 6. - i=2 (coin=4): count += 6/4 = 1, amount = 6%4 = 2 - i=1 (coin=3): count += 2/3 = 0, amount = 2%3 = 2 - i=0 (coin=1): count += 2/1 = 2, amount = 2%1 = 0 Total count = 1 + 0 + 2 = 3.

2. Step 2: Confirm output

   The Console.WriteLine prints 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Greedy coin count = 3 [OK]

Hint: Trace loops step-by-step to find output [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Miscomputing division or modulo
• Ignoring order of coins in loop

4. The following code tries to solve the coin change problem using DP but has a bug. What is the error?

int[] coins = {1, 3, 4};
int amount = 6;
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++)
{
    dp[i] = int.MaxValue;
    foreach (int coin in coins)
    {
        if (i - coin >= 0)
        {
            dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
        }
    }
}
Console.WriteLine(dp[amount]);

medium

A. int.MaxValue causes overflow when adding 1

B. dp array is not initialized properly for base case

C. Coins array is not sorted

D. Loop indices are incorrect

Solution

1. Step 1: Understand dp initialization and update

   dp[i] is set to int.MaxValue initially. When dp[i - coin] is int.MaxValue, adding 1 causes overflow.

2. Step 2: Identify overflow problem

   Adding 1 to int.MaxValue wraps around to negative, causing wrong minimum calculation.

3. Final Answer:

   int.MaxValue causes overflow when adding 1 -> Option A

4. Quick Check:

   Adding 1 to int.MaxValue overflows [OK]

Hint: Avoid adding to int.MaxValue directly [OK]

Common Mistakes:

• Ignoring overflow from int.MaxValue + 1
• Assuming coin order matters in DP
• Not initializing dp[0] correctly

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

// Greedy approach
int count = 0;
int amount = 6;
int[] coins = {4, 3, 1};
for (int i = 0; i < coins.Length; i++)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

Choose the best answer.

hard

A. Greedy works because coins are sorted descending

B. Neither approach works for this problem

C. Both greedy and DP give same result here

D. Greedy fails; DP is better due to overlapping subproblems

Solution

1. Step 1: Test greedy approach output

   Greedy picks 4 once (6/4=1), remainder 2, picks 3 (2/3=0), remainder 2, picks 1 (2/1=2), total coins = 3.

2. Step 2: Check if greedy is optimal

   DP finds minimum coins: 2 (4 + 2 coins). Greedy gives 3, suboptimal.

3. Step 3: Consider general case

   Greedy can fail for some amounts; DP handles overlapping subproblems and finds true minimum.

4. Final Answer:

   Greedy fails; DP is better due to overlapping subproblems -> Option D

5. Quick Check:

   Overlapping subproblems need DP, greedy may fail [OK]

Hint: Use DP if greedy might miss optimal solution [OK]

Common Mistakes:

• Assuming greedy always works if coins sorted
• Ignoring overlapping subproblems in coin change
• Thinking greedy and DP always match