Greedy vs DP How to Know Which to Apply in DSA Java - Trade-offs & Analysis

Mental Model

Greedy picks the best choice now, hoping it leads to the best overall. DP looks at all choices and remembers past results to find the best overall.

Analogy: Choosing snacks: greedy is like grabbing the tastiest snack first without thinking ahead; DP is like planning your snacks for the whole day to maximize happiness.

Choices: [1] -> [2] -> [3] -> [4] -> null
Greedy: picks one step at a time ->
DP: remembers best results from previous steps ↑

Dry Run Walkthrough

Input: Problem: Choose coins to make 6 cents from coins [1, 3, 4].

Goal: Find minimum coins needed using greedy and DP to see which works.

Step 1: Greedy picks largest coin ≤ 6, which is 4.

Chosen coins: 4 -> remaining 2

Why: Greedy tries best immediate choice to reduce amount quickly.

Step 2: Greedy picks largest coin ≤ 2, which is 1.

Chosen coins: 4 -> 1 -> remaining 1

Why: Greedy continues picking largest coin possible.

Step 3: Greedy picks largest coin ≤ 1, which is 1.

Chosen coins: 4 -> 1 -> 1 -> remaining 0

Why: Greedy finishes by picking smallest coin.

Step 4: DP tries all coins for amount 6, remembers best results for smaller amounts.

DP table: minCoins[0]=0, minCoins[1]=1, minCoins[2]=2, minCoins[3]=1, minCoins[4]=1, minCoins[5]=2, minCoins[6]=2

Why: DP builds solution bottom-up considering all options.

Step 5: DP finds minimum coins for 6 is 2 (coins 3 + 3).

Chosen coins by DP: 3 -> 3 -> remaining 0

Why: DP finds better solution than greedy here.

Result:

Greedy chosen coins: 4 -> 1 -> 1 -> null (3 coins)
DP chosen coins: 3 -> 3 -> null (2 coins)
DP gives better answer here.

Annotated Code

DSA Java

import java.util.*;

public class CoinChange {
    // DP method to find min coins
    public static int minCoinsDP(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // large number
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); // update min coins
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    // Greedy method to find coins count
    public static int greedyCoins(int amount, int[] coins) {
        int count = 0;
        int remaining = amount;
        Arrays.sort(coins);
        for (int i = coins.length - 1; i >= 0; i--) {
            while (coins[i] <= remaining) {
                remaining -= coins[i]; // pick coin
                count++;
            }
        }
        return remaining == 0 ? count : -1; // -1 if no exact change
    }

    public static void main(String[] args) {
        int amount = 6;
        int[] coins = {1, 3, 4};
        int greedyResult = greedyCoins(amount, coins);
        int dpResult = minCoinsDP(amount, coins);
        System.out.println("Greedy chosen coins count: " + greedyResult);
        System.out.println("DP chosen coins count: " + dpResult);
    }
}

dp[i] = Math.min(dp[i], dp[i - coin] + 1);

update dp[i] with minimum coins using current coin

while (coins[i] <= remaining) { remaining -= coins[i]; count++; }

greedy picks largest coin repeatedly until it can't

Output

Greedy chosen coins count: 3

DP chosen coins count: 2

Complexity Analysis

Time: O(n * amount) because DP tries all coins for each amount up to target

Space: O(amount) for DP array storing minimum coins for each amount

vs Alternative: Greedy is faster O(n log n) due to sorting and simple picks but can fail; DP is slower but always correct

Edge Cases

Amount zero

Both greedy and DP return 0 coins needed

DSA Java

dp[0] = 0;

No coin can make amount exactly

Both return -1 indicating no solution

DSA Java

return dp[amount] > amount ? -1 : dp[amount];

Single coin equal to amount

Both return 1 coin needed

DSA Java

while (coins[i] <= remaining) { remaining -= coins[i]; count++; }

When to Use This Pattern

When a problem asks for optimal choices and greedy fails on some inputs, try DP because it explores all options and remembers results.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution
Fix: Test with examples where greedy fails and use DP to guarantee correctness

Mistake: Not sorting coins before greedy approach
Fix: Sort coins descending to pick largest first in greedy

Summary

Greedy picks best immediate choice hoping for global best; DP tries all choices and remembers past results.

Use greedy when problem has 'greedy choice property' and no overlapping subproblems; use DP when problem has overlapping subproblems and optimal substructure.

The key insight is that greedy is fast but sometimes wrong; DP is slower but always finds the best answer.

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