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 Greedy works?

↓

Apply [Check if DP applies

Start by checking if greedy choice leads to optimal solution. If not, check if problem has overlapping subproblems and optimal substructure for DP.

Execution Sample

DSA C

int maxSumGreedy(int arr[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (arr[i] > 0) sum += arr[i];
  }
  return sum;
}

This code sums all positive numbers greedily, assuming picking positive numbers always leads to max sum.

Execution Table

Step	Operation	Current Index	Sum Before	Condition arr[i]>0	Sum After	Explanation
1	Initialize sum	-	0	-	0	Start with sum = 0
2	Check arr[0]	0	0	arr[0] = 3 > 0: True	3	Add 3 to sum
3	Check arr[1]	1	3	arr[1] = -1 > 0: False	3	Skip -1
4	Check arr[2]	2	3	arr[2] = 4 > 0: True	7	Add 4 to sum
5	Check arr[3]	3	7	arr[3] = 2 > 0: True	9	Add 2 to sum
6	Check arr[4]	4	9	arr[4] = -5 > 0: False	9	Skip -5
7	Return sum	-	9	-	9	Final sum is 9

💡 All elements checked, sum of positive numbers returned

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
sum	0	3	3	7	9	9	9
i	-	0	1	2	3	4	-

Key Moments - 2 Insights

Why does greedy fail if the problem needs to consider future choices?

Because greedy only looks at the current best choice (see Step 3 and 6 where negative numbers are skipped), it may miss better overall solutions that require considering future elements, which DP handles by exploring all subproblems.

How do I know if DP applies instead of greedy?

If the problem has overlapping subproblems and optimal substructure (meaning the best solution depends on solutions to smaller parts), DP is suitable. Greedy works only if local optimal choices lead to global optimum (see concept_flow decision).

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum after checking index 2?

A 9

B 3

C 7

D 4

💡 Hint

Check the 'Sum After' column at Step 4 in execution_table

At which step does the condition arr[i] > 0 become false for the first time?

A Step 3

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Condition arr[i]>0' column in execution_table rows

If the array had all negative numbers, what would the greedy sum be?

A Sum of all negatives

B Zero

C Sum of absolute values

D Undefined

💡 Hint

Refer to variable_tracker 'sum' values and the condition that only adds positive numbers

Concept Snapshot

Greedy vs DP Decision:
- Greedy picks local best choices step-by-step.
- Works only if local choices lead to global best.
- DP solves by combining solutions of subproblems.
- Use DP if problem has overlapping subproblems and optimal substructure.
- Check problem properties before choosing approach.

Full Transcript

This visual trace shows how a greedy approach sums positive numbers in an array by checking each element and adding it if positive. The concept flow guides deciding between greedy and dynamic programming (DP) by checking if greedy choices lead to optimal solution or if DP is needed for overlapping subproblems. The execution table tracks each step, condition, and sum updates. Key moments clarify why greedy can fail and when DP is better. The quiz tests understanding of sum updates and condition checks. The snapshot summarizes how to choose between greedy and DP based on problem properties.

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 combinations

C. When the problem has overlapping subproblems but no greedy choice

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: Compare with dynamic programming conditions

   Dynamic programming is used when subproblems overlap and greedy choice property does not hold.

3. Final Answer:

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

4. Quick Check:

   Greedy choice property = Use greedy [OK]

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

Common Mistakes:

• Confusing overlapping subproblems with greedy choice
• Using greedy when problem needs full exploration
• Assuming sorting problems always need greedy

2. Which of the following is the correct syntax to declare a memoization array for dynamic programming in C?

easy

A. int memo[1000] = {0};

B. int memo[] = 0;

C. int memo(1000) = {0};

D. int memo = new int[1000];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization using braces.

2. Step 2: Check each option

   int memo[1000] = {0}; correctly declares an int array of size 1000 initialized to zero. Others are invalid C syntax.

3. Final Answer:

   int memo[1000] = {0}; -> Option A

4. Quick Check:

   C arrays use [] with size [OK]

Hint: Use int arr[size] = {0} for zero-initialized arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Trying to assign 0 directly to array
• Using new keyword in C (it's C++ syntax)

3. What is the output of the following C code snippet that uses a greedy approach to select coins?

int coins[] = {1, 5, 10, 25};
int amount = 30;
int count = 0;
for (int i = 3; i >= 0; i--) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("%d\n", count);

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace the greedy coin selection

   Start with coin 25: amount=30, 30>=25, subtract 25, amount=5, count=1.

2. Step 2: Continue with smaller coins

   Next coin 10: amount=5<10, skip. Next coin 5: amount=5>=5, subtract 5, amount=0, count=2.

3. Step 3: No more coins needed

   Loop ends, total coins used = 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   25 + 5 = 30 using 2 coins [OK]

Hint: Subtract largest coin repeatedly until amount zero [OK]

Common Mistakes:

• Counting coins incorrectly in loops
• Not updating amount after subtraction
• Confusing coin order in loop

4. The following code attempts to solve the Fibonacci sequence using a greedy approach. What is the error?

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

medium

A. Loop should start from i = 1 instead of 2

B. No error, code correctly computes Fibonacci

C. Variable c is not initialized properly

D. Greedy approach is incorrect for Fibonacci calculation

Solution

1. Step 1: Understand Fibonacci calculation

   Fibonacci requires summing previous two numbers, which is a classic dynamic programming problem.

2. Step 2: Identify greedy approach misuse

   The code uses iteration correctly but calling it greedy is wrong because Fibonacci does not have greedy choice property.

3. Final Answer:

   Greedy approach is incorrect for Fibonacci calculation -> Option D

4. Quick Check:

   Fibonacci needs DP, not greedy [OK]

Hint: Fibonacci needs DP, greedy won't work [OK]

Common Mistakes:

• Thinking iterative is greedy
• Ignoring problem properties
• Confusing initialization with error

5. You want to find the minimum number of coins to make change for a given amount using coins of denominations {1, 3, 4}. Which approach is best and why?

hard

A. Greedy, because always picking the largest coin works here

B. Dynamic Programming, because greedy fails for some amounts

C. Brute force, because both greedy and DP are too complex

D. Sorting coins and picking smallest first

Solution

1. Step 1: Test greedy approach on example

   For amount 6, greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

2. Step 2: Recognize overlapping subproblems

   Dynamic programming stores solutions for smaller amounts to build up answer correctly.

3. Step 3: Conclude best approach

   Greedy fails due to lack of greedy choice property; DP handles all cases optimally.

4. Final Answer:

   Dynamic Programming, because greedy fails for some amounts -> Option B

5. Quick Check:

   Greedy fails, DP works [OK]

Hint: Test greedy on small cases; if fails, use DP [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring counterexamples
• Choosing brute force unnecessarily