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

Mental Model

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

Analogy: Imagine choosing snacks from a buffet: greedy is like grabbing the tastiest snack you see first, while DP is like trying small bites of all snacks and remembering which combination tastes best together.

Choices: [1] [2] [3] [4]
Greedy: pick -> [2] -> [4]
DP: explore all combos -> [1,3] or [2,4]

Dry Run Walkthrough

Input: Problem: Choose coins to make 6 cents with coins 1, 3, 4 cents. Goal: Find minimum coins needed.

Goal: Decide if greedy or DP works and find minimum coins.

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

Chosen coins: 4
Remaining: 2

Why: Greedy tries best immediate choice.

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

Chosen coins: 4 -> 1
Remaining: 1

Why: Greedy repeats best immediate choice.

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

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

Why: Greedy finishes with smallest coin.

Step 4: DP tries all combos: 3 + 3 = 6 with 2 coins.

DP finds coins: 3 -> 3
Total coins: 2

Why: DP explores all to find fewer coins.

Result:

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

Annotated Code

DSA Rust

struct CoinChange {
    coins: Vec<usize>,
}

impl CoinChange {
    fn greedy_min_coins(&self, amount: usize) -> Option<Vec<usize>> {
        let mut remaining = amount;
        let mut result = Vec::new();
        let mut sorted_coins = self.coins.clone();
        sorted_coins.sort_by(|a, b| b.cmp(a));
        while remaining > 0 {
            let mut found = false;
            for &coin in &sorted_coins {
                if coin <= remaining {
                    result.push(coin); // pick coin
                    remaining -= coin; // reduce amount
                    found = true;
                    break; // pick one coin at a time
                }
            }
            if !found {
                return None; // no coin fits
            }
        }
        Some(result)
    }

    fn dp_min_coins(&self, amount: usize) -> Option<Vec<usize>> {
        let mut dp = vec![None; amount + 1];
        dp[0] = Some(Vec::new());
        for i in 1..=amount {
            for &coin in &self.coins {
                if coin <= i {
                    if let Some(prev) = &dp[i - coin] {
                        let mut new_combo = prev.clone();
                        new_combo.push(coin); // add coin
                        if dp[i].is_none() || dp[i].as_ref().unwrap().len() > new_combo.len() {
                            dp[i] = Some(new_combo); // keep shortest combo
                        }
                    }
                }
            }
        }
        dp[amount].clone()
    }
}

fn main() {
    let cc = CoinChange { coins: vec![1, 3, 4] };
    let amount = 6;
    if let Some(greedy_res) = cc.greedy_min_coins(amount) {
        println!("Greedy coins: {} -> null", greedy_res.iter().map(|c| c.to_string()).collect::<Vec<_>>().join(" -> "));
    } else {
        println!("Greedy: no solution");
    }
    if let Some(dp_res) = cc.dp_min_coins(amount) {
        println!("DP coins: {} -> null", dp_res.iter().map(|c| c.to_string()).collect::<Vec<_>>().join(" -> "));
    } else {
        println!("DP: no solution");
    }
}

for &coin in &sorted_coins { if coin <= remaining { result.push(coin); remaining -= coin; break; } }

pick largest coin fitting remaining amount to reduce it greedily

dp[0] = Some(Vec::new());

base case: zero amount needs zero coins

for i in 1..=amount { for &coin in &self.coins { if coin <= i { if let Some(prev) = &dp[i - coin] { let mut new_combo = prev.clone(); new_combo.push(coin); if dp[i].is_none() || dp[i].as_ref().unwrap().len() > new_combo.len() { dp[i] = Some(new_combo); } } } } }

try all coins for each amount, keep shortest coin combo

Output

Greedy coins: 4 -> 1 -> 1 -> null

DP coins: 3 -> 3 -> null

Complexity Analysis

Time: Greedy: O(n) because it tries coins once in descending order; DP: O(n * amount) because it tries all coins for all amounts up to target

Space: Greedy: O(n) for result list; DP: O(amount * n) for dp table storing combinations

vs Alternative: Greedy is faster but can fail to find best solution; DP is slower but always finds optimal solution by exploring all possibilities

Edge Cases

amount zero

Both greedy and DP return empty list (no coins needed)

DSA Rust

dp[0] = Some(Vec::new());

no coin fits amount

Greedy returns None when no coin fits remaining; DP returns None if no combination found

DSA Rust

if !found { return None; }

coins with duplicates

Algorithm still works correctly as duplicates do not affect logic

DSA Rust

for &coin in &self.coins

When to Use This Pattern

When a problem asks for an optimal solution and greedy choices might fail, try DP to explore all options and remember results; if greedy always works, use it for speed.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution without checking problem properties
Fix: Test greedy on small examples; if it fails, switch to DP

Summary

Greedy picks best immediate choice; DP tries all choices and remembers results.

Use greedy when local best choices lead to global best; use DP when problem has overlapping subproblems and optimal substructure.

The key is to test if greedy fails on small cases; if yes, DP is needed.

Practice

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

easy

A. When the problem has overlapping subproblems and no optimal substructure

B. When the problem has an optimal substructure and no overlapping subproblems

C. When the problem requires checking all possible solutions

D. When the problem is unsolvable

Solution

1. Step 1: Understand greedy algorithm conditions

   Greedy algorithms work when choosing the best option at each step leads to a global optimum, which means the problem has an optimal substructure and no overlapping subproblems.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when the problem has overlapping subproblems and optimal substructure, requiring storing intermediate results.

3. Final Answer:

   When the problem has an optimal substructure and no overlapping subproblems -> Option B

4. Quick Check:

   Greedy = optimal substructure + no overlap [OK]

Hint: Use greedy if no overlapping subproblems exist [OK]

Common Mistakes:

• Confusing overlapping subproblems as a greedy condition
• Using DP when greedy suffices
• Assuming greedy always finds optimal solution
• Ignoring problem structure before choosing approach

2. Which Rust code snippet correctly declares a vector and uses it to implement a greedy approach for selecting intervals sorted by end time?

easy

A. let intervals = vec![(1,3), (2,5), (4,7)]; intervals.reverse();

B. let intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort();

C. let mut intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort_by(|a,b| a.0.cmp(&b.0));

D. let mut intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort_by_key(|k| k.1);

Solution

1. Step 1: Identify correct vector declaration and sorting

   let mut intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort_by_key(|k| k.1); declares a mutable vector and sorts it by the second element (end time), which is needed for greedy interval scheduling.

2. Step 2: Check other options for correctness

   let intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort(); tries to sort an immutable vector and uses default sort (by first element), let mut intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort_by(|a,b| a.0.cmp(&b.0)); sorts by start time, not end time, and let intervals = vec![(1,3), (2,5), (4,7)]; intervals.reverse(); reverses without sorting.

3. Final Answer:

   let mut intervals = vec![(1,3), (2,5), (4,7)]; intervals.sort_by_key(|k| k.1); -> Option D

4. Quick Check:

   Sort intervals by end time with mutable vector [OK]

Hint: Sort intervals by end time for greedy scheduling [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Using immutable vector when sorting is needed
• Not sorting intervals before greedy selection
• Using reverse instead of sort

3. What is the output of the following Rust code implementing a greedy approach to select maximum intervals?

let mut intervals = vec![(1,3), (2,5), (4,7)];
intervals.sort_by_key(|k| k.1);
let mut count = 0;
let mut end = 0;
for &(start, finish) in &intervals {
    if start >= end {
        count += 1;
        end = finish;
    }
}
println!("{}", count);

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: (1,3), (2,5), (4,7)

2. Step 2: Iterate and count non-overlapping intervals

   First interval (1,3): start=1 >= end=0, count=1, end=3 Second interval (2,5): start=2 < end=3, skip Third interval (4,7): start=4 >= end=3, count=2, end=7

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Greedy interval count = 2 [OK]

Hint: Count intervals where start >= last end [OK]

Common Mistakes:

• Counting overlapping intervals
• Not updating end after selection
• Sorting incorrectly
• Confusing start and end values

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

let coins = vec![1, 3, 4];
let mut amount = 6;
let mut count = 0;
for &coin in coins.iter().rev() {
    while amount >= coin {
        amount -= coin;
        count += 1;
    }
}
println!("{}", count);

medium

A. The amount variable is not mutable

B. The coins vector is not sorted ascending

C. Greedy fails because coin denominations do not guarantee optimal solution

D. The loop should not reverse the coins vector

Solution

1. Step 1: Understand greedy coin change limitation

   Greedy works only if coin denominations are canonical (like 1,5,10). Here, 1,3,4 can cause greedy to fail.

2. Step 2: Check code behavior

   Greedy picks 4 once (amount=2), then picks 1 twice (total 3 coins). But optimal is 2 coins (3+3).

3. Final Answer:

   Greedy fails because coin denominations do not guarantee optimal solution -> Option C

4. Quick Check:

   Greedy fails on non-canonical coins [OK]

Hint: Greedy fails if coin set is not canonical [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring coin order importance
• Not checking for optimal substructure
• Confusing mutability of variables

5. You want to find the minimum number of coins to make amount 6 using coins [1, 3, 4]. Which approach is best and why? A) Greedy picking largest coin first B) Brute force checking all combinations C) Dynamic programming storing minimum coins for each amount D) Sorting coins ascending and picking smallest first

hard

A. Dynamic programming storing minimum coins for each amount

B. Brute force checking all combinations

C. Greedy picking largest coin first

D. Sorting coins ascending and picking smallest first

Solution

1. Step 1: Analyze greedy approach limitations

   Greedy may pick 4 then 1s, resulting in 3 coins, but optimal is 2 coins (3+3).

2. Step 2: Understand dynamic programming advantage

   DP stores minimum coins needed for each amount, ensuring optimal solution even with tricky coin sets.

3. Step 3: Compare other options

   Brute force is slow; sorting ascending and picking smallest first is not optimal strategy.

4. Final Answer:

   Dynamic programming storing minimum coins for each amount -> Option A

5. Quick Check:

   DP handles overlapping subproblems for optimal coin count [OK]

Hint: Use DP for minimum coins with tricky denominations [OK]

Common Mistakes:

• Using greedy for non-canonical coin sets
• Ignoring performance of brute force
• Assuming sorting smallest first helps
• Not recognizing overlapping subproblems