Greedy vs DP How to Know Which to Apply in DSA Java - 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

↓

Solution

Start by checking if the problem has optimal substructure. Then check if subproblems overlap. Use DP if yes, else greedy.

Execution Sample

DSA Java

if (hasOptimalSubstructure && hasOverlappingSubproblems) {
    useDP();
} else if (hasOptimalSubstructure) {
    useGreedy();
} else {
    noSimpleSolution();
}

Decide between DP and Greedy based on problem properties.

Execution Table

Step	Check	Condition	Result	Action	Reasoning
1	Check optimal substructure	true	Yes	Proceed to next check	Problem can be broken into subproblems with optimal solutions
2	Check overlapping subproblems	true	Yes	Choose DP	Subproblems repeat, so store results to avoid recomputation
3	Build solution	N/A	N/A	Use DP approach	Use memoization or tabulation to build final answer
4	End	N/A	N/A	Solution found	DP chosen due to overlapping subproblems
5	Alternate scenario	overlapping subproblems = false	No	Choose Greedy	No repeated subproblems, greedy local choices lead to global optimum
6	Build solution	N/A	N/A	Use Greedy approach	Pick best local option at each step
7	End	N/A	N/A	Solution found	Greedy chosen due to no overlapping subproblems

💡 Decision ends when either DP or Greedy is chosen based on problem properties

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
hasOptimalSubstructure	unknown	true	true	true
hasOverlappingSubproblems	unknown	unknown	true	true
chosenMethod	none	none	DP	DP

Key Moments - 3 Insights

Why do we check for optimal substructure first?

Because both greedy and DP require the problem to be broken into smaller optimal subproblems. Without this, neither method applies well. See execution_table step 1.

What does overlapping subproblems mean and why does it matter?

It means the same smaller problems appear multiple times. DP stores results to avoid repeated work. Greedy does not handle this. See execution_table steps 2 and 5.

Can greedy always replace DP if optimal substructure exists?

No. Greedy only works if local best choices lead to global best. If overlapping subproblems exist, DP is safer. See execution_table steps 2 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, at which step do we decide to use DP?

A Step 1

B Step 2

C Step 5

D Step 7

💡 Hint

Check the 'Action' column where 'Choose DP' appears.

According to variable_tracker, what is the value of 'chosenMethod' after Step 2?

A none

B Greedy

C DP

D unknown

💡 Hint

Look at the 'chosenMethod' row under 'After Step 2' column.

If overlapping subproblems were false, which method would be chosen according to execution_table?

A Greedy

B DP

C No simple solution

D Brute force

💡 Hint

See execution_table step 5 where overlapping subproblems = false.

Concept Snapshot

Greedy vs DP Decision:
1. Check optimal substructure: problem breaks into optimal subproblems.
2. Check overlapping subproblems: repeated subproblems?
3. If yes, use DP (store results).
4. If no, use Greedy (local best choices).
5. If no optimal substructure, no simple solution.
Use this flow to pick the right approach.

Full Transcript

To decide between Greedy and Dynamic Programming (DP), first check if the problem has optimal substructure, meaning it can be broken into smaller subproblems whose solutions build the overall solution. If this is true, then check if the problem has overlapping subproblems, meaning the same subproblems appear multiple times. If overlapping subproblems exist, use DP to store and reuse results, avoiding repeated work. If not, use Greedy, which picks the best local choice at each step to reach the global optimum. If the problem lacks optimal substructure, neither method applies simply. This decision flow helps choose the right method for efficient problem solving.

Practice

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

easy

A. When the problem needs to store all intermediate results

B. When the problem requires checking all possible combinations

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

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

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: Recognize 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 D

4. Quick Check:

   Greedy = greedy choice + optimal substructure [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
• Ignoring optimal substructure requirement

2. Which Java syntax correctly declares a 2D array for dynamic programming table initialization?

easy

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

B. int dp[][] = new int(5,5);

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

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

Solution

1. Step 1: Recall Java 2D array syntax

   Java uses new int[rows][columns] to declare 2D arrays.

2. Step 2: Check each option

   int[][] dp = new int[5][5]; uses correct syntax. Options A, B, C have syntax errors or incomplete declarations.

3. Final Answer:

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

4. Quick Check:

   Correct 2D array declaration = int[][] dp = new int[5][5]; [OK]

Hint: Use new int[rows][cols] for 2D arrays in Java [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Missing size in second dimension
• Incorrect array initialization syntax

3. What is the output of the following Java code snippet?

int[] coins = {1, 2, 5};
int amount = 11;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
    count += amount / coins[i];
    amount %= coins[i];
}
System.out.println(count);

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace the loop from largest coin to smallest

   Start with amount=11, coins = [1,2,5]. i=2 (coin=5): count += 11/5=2, amount=11%5=1.

2. Step 2: Continue with next coins

   i=1 (coin=2): count += 1/2=0, amount=1%2=1; i=0 (coin=1): count += 1/1=1, amount=1%1=0.

3. Step 3: Calculate total count

   Total count = 2 + 0 + 1 = 3.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   Greedy coin count = 3 [OK]

Hint: Divide and mod with largest coin first [OK]

Common Mistakes:

• Adding counts incorrectly
• Mixing up division and modulo
• Ignoring order of coins

4. The following code attempts to solve the coin change problem using greedy approach. What is the bug?

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];
}
System.out.println(count);

medium

A. Division by zero error

B. Greedy fails because coin set lacks greedy choice property

C. Array index out of bounds error

D. Incorrect initialization of count variable

Solution

1. Step 1: Understand greedy choice property failure

   Coins {1,3,4} do not guarantee greedy choice property for amount 6.

2. Step 2: Trace greedy approach output

   Greedy picks 4 once (count=1), remainder 2; then picks two 1s (count=3). But optimal is two 3s (count=2).

3. Final Answer:

   Greedy fails because coin set lacks greedy choice property -> Option B

4. Quick Check:

   Greedy fails if no greedy choice property [OK]

Hint: Check if greedy choice property holds before using greedy [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring optimal substructure requirement
• Confusing runtime errors with logic errors

5. Given a set of tasks with start and end times, which approach is best to find the maximum number of non-overlapping tasks?

class Task {
    int start, end;
    Task(int s, int e) { start = s; end = e; }
}

Choose the correct approach and why.

hard

A. Use greedy by sorting tasks by earliest finish time to select tasks

B. Use dynamic programming to check all subsets of tasks

C. Use greedy by sorting tasks by longest duration first

D. Use dynamic programming to store maximum tasks ending at each time

Solution

1. Step 1: Identify problem type

   This is the activity selection problem, classic greedy example.

2. Step 2: Choose greedy approach

   Sorting by earliest finish time ensures maximum tasks without overlap.

3. Step 3: Compare options

   Use greedy by sorting tasks by earliest finish time to select tasks matches known greedy solution; DP is possible but less efficient here.

4. Final Answer:

   Use greedy by sorting tasks by earliest finish time to select tasks -> Option A

5. Quick Check:

   Activity selection = greedy by finish time [OK]

Hint: Sort tasks by finish time for max non-overlapping tasks [OK]

Common Mistakes:

• Sorting by start time or duration instead of finish time
• Using DP unnecessarily increasing complexity
• Ignoring greedy choice property in scheduling