Greedy vs DP How to Know Which to Apply in DSA C# - Visual Comparison

Concept Flow - Greedy vs DP How to Know Which to Apply

Start Problem

↓

Check if problem has optimal substructure?

Yes↓

Check if problem has overlapping subproblems?

Yes No↓

Use DP

↓

Build solution using stored results

↓

Get final answer

Decide approach by checking if problem has optimal substructure and overlapping subproblems; use DP if both, else greedy.

Execution Sample

DSA C#

bool HasOptimalSubstructure = true;
bool HasOverlappingSubproblems = false;

if (HasOptimalSubstructure) {
  if (HasOverlappingSubproblems) {
    Console.WriteLine("Use DP");
  } else {
    Console.WriteLine("Use Greedy");
  }
} else {
  Console.WriteLine("Neither Greedy nor DP fits well");
}

This code decides whether to use Greedy or DP based on problem properties.

Execution Table

Step	Check	Condition	Result	Action	Output
1	HasOptimalSubstructure	true	Yes	Check HasOverlappingSubproblems
2	HasOverlappingSubproblems	false	No	Choose Greedy	Use Greedy
3	End	-	-	Stop	Use Greedy

💡 HasOptimalSubstructure true but HasOverlappingSubproblems false, so Greedy is chosen.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
HasOptimalSubstructure	true	true	true	true
HasOverlappingSubproblems	false	false	false	false
Decision	none	none	Greedy	Greedy

Key Moments - 3 Insights

Why do we check for optimal substructure first?

Because both Greedy and DP require optimal substructure; if it's missing, neither approach fits well. See execution_table step 1.

What does overlapping subproblems mean and why does it matter?

Overlapping subproblems means the problem repeats the same smaller problems. DP uses this to store results and avoid recomputation. Greedy does not need this. See execution_table step 2.

Can we use Greedy if overlapping subproblems exist?

Usually no, because Greedy makes local choices without storing past results. If overlapping subproblems exist, DP is safer. See execution_table step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the decision at step 2?

A Use DP

B Use Greedy

C Neither

D Check again

💡 Hint

Check the 'Action' and 'Output' columns at step 2 in execution_table.

At which step do we check if the problem has overlapping subproblems?

A Step 2

B Step 1

C Step 3

D Before Step 1

💡 Hint

Look at the 'Check' column in execution_table to see when HasOverlappingSubproblems is checked.

If HasOverlappingSubproblems was true, what would the output be at step 2?

A Use Greedy

B Neither

C Use DP

D Stop

💡 Hint

Refer to the concept_flow where overlapping subproblems true leads to DP.

Concept Snapshot

Check if problem has optimal substructure (solutions build from sub-solutions).
If yes, check for overlapping subproblems (repeated subproblems).
If both yes, use Dynamic Programming (store and reuse results).
If only optimal substructure yes, use Greedy (choose best local option).
If no optimal substructure, neither fits well.
This guides choosing between Greedy and DP.

Full Transcript

To decide between Greedy and Dynamic Programming (DP), first check if the problem has optimal substructure, meaning the best solution can be built from best solutions of smaller parts. If it does not, neither Greedy nor DP is suitable. If it does, then check if the problem has overlapping subproblems, meaning the same smaller problems repeat. If yes, DP is best because it stores results to avoid repeated work. If no, Greedy works by making the best local choice at each step. This decision flow helps pick the right approach for a problem.

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