Greedy vs DP How to Know Which to Apply in DSA C# - Key Differences

Recall & Review

beginner

What is the main idea behind the greedy approach?

The greedy approach makes the best choice at each step, hoping to find the overall best solution without reconsidering previous choices.

beginner

What does Dynamic Programming (DP) do differently from greedy algorithms?

DP solves problems by breaking them into smaller overlapping subproblems, storing their results, and combining them to find the best overall solution.

intermediate

When should you choose a greedy algorithm over DP?

Choose greedy when the problem has the greedy-choice property and optimal substructure, meaning local best choices lead to a global best solution.

beginner

What is the 'optimal substructure' property?

A problem has optimal substructure if an optimal solution can be built from optimal solutions of its subproblems.

intermediate

How can you test if a greedy algorithm will work for a problem?

Check if making the best local choice at each step always leads to a global optimum. If not, DP might be needed.

Which property must a problem have for a greedy algorithm to guarantee an optimal solution?

A Memoization

B Overlapping subproblems

C Greedy-choice property

D Backtracking

The greedy-choice property means local optimal choices lead to a global optimum, which is essential for greedy algorithms.

Dynamic Programming is best used when a problem has:

A Overlapping subproblems and optimal substructure

B Greedy-choice property only

C No subproblems

D Only one solution path

DP works well when problems have overlapping subproblems and optimal substructure.

Which approach stores results of subproblems to avoid repeated work?

A Greedy

B Dynamic Programming

C Brute Force

D Divide and Conquer

Dynamic Programming stores subproblem results to avoid recomputation.

If a problem’s local best choice does NOT always lead to a global best, which method is preferred?

A Greedy

B Binary Search

C Linear Search

D Dynamic Programming

DP handles cases where local choices don’t guarantee global optimum.

Which of these is NOT a characteristic of greedy algorithms?

A Reconsider previous choices

B Works when greedy-choice property holds

C Fast and simple

D Make decisions step-by-step

Greedy algorithms do NOT reconsider previous choices once made.

Explain how to decide between using a greedy algorithm or dynamic programming for a problem.

Think about whether local best choices lead to global best and if subproblems repeat.

Describe the key differences between greedy algorithms and dynamic programming.

Focus on how each approach handles problem solving and decision making.

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