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.