Greedy vs DP How to Know Which to Apply in DSA Typescript - 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] -> null
Greedy: picks one at a time -> best now
DP: explores all paths -> remembers best

Dry Run Walkthrough

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

Goal: Decide if greedy or DP works better to find minimum coins needed

Step 1: Greedy picks largest coin ≤ 6, picks 4

Chosen: 4 -> Remaining: 2

Why: Greedy tries best immediate choice to reduce amount quickly

Step 2: Greedy picks largest coin ≤ 2, picks 1

Chosen: 4 -> 1 -> Remaining: 1

Why: Greedy continues picking largest coin possible

Step 3: Greedy picks largest coin ≤ 1, picks 1

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

Why: Greedy finishes when amount is zero

Step 4: DP tries all combinations and finds 3 + 3 = 6 with 2 coins

Best: 3 -> 3 -> null (2 coins)

Why: DP explores all options and remembers best results

Result:

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

Annotated Code

DSA Typescript

class CoinChange {
  coins: number[];
  constructor(coins: number[]) {
    this.coins = coins;
  }

  greedyChange(amount: number): number[] {
    const result: number[] = [];
    let remaining = amount;
    this.coins.sort((a, b) => b - a); // largest first
    while (remaining > 0) {
      let coin = this.coins.find(c => c <= remaining);
      if (coin === undefined) break;
      result.push(coin);
      remaining -= coin;
    }
    return result;
  }

  dpChange(amount: number): number[] {
    const dp: number[] = Array(amount + 1).fill(Infinity);
    const backtrack: number[] = Array(amount + 1).fill(-1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
      for (const coin of this.coins) {
        if (coin <= i && dp[i - coin] + 1 < dp[i]) {
          dp[i] = dp[i - coin] + 1;
          backtrack[i] = coin;
        }
      }
    }
    if (dp[amount] === Infinity) return [];
    const result: number[] = [];
    let curr = amount;
    while (curr > 0) {
      result.push(backtrack[curr]);
      curr -= backtrack[curr];
    }
    return result;
  }
}

const coins = [1, 3, 4];
const amount = 6;
const cc = new CoinChange(coins);
const greedyResult = cc.greedyChange(amount);
const dpResult = cc.dpChange(amount);
console.log('Greedy picks coins:', greedyResult.join(' -> ') + ' -> null');
console.log('DP picks coins:', dpResult.join(' -> ') + ' -> null');

this.coins.sort((a, b) => b - a); // largest first

sort coins descending to pick largest first in greedy

let coin = this.coins.find(c => c <= remaining);

pick largest coin not exceeding remaining amount

dp[0] = 0;

base case: zero coins needed for amount zero

if (coin <= i && dp[i - coin] + 1 < dp[i]) {

update dp if using coin reduces coin count for amount i

result.push(backtrack[curr]); curr -= backtrack[curr];

reconstruct chosen coins from backtrack array

Output

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

DP picks coins: 3 -> 3 -> null

Complexity Analysis

Time: Greedy: O(n log n) due to sorting coins; DP: O(n * amount) because it tries all coins for each amount up to target

Space: Greedy: O(n) for result; DP: O(amount) for dp and backtrack arrays

vs Alternative: Greedy is faster but can fail to find optimal; DP is slower but always finds optimal solution

Edge Cases

Amount zero

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

DSA Typescript

dp[0] = 0;

No coins smaller than amount

Greedy returns partial or empty; DP returns empty indicating no solution

DSA Typescript

if (coin === undefined) break;

Coins with duplicates

Both methods handle duplicates correctly as they consider all coins

DSA Typescript

for (const coin of this.coins) {

When to Use This Pattern

When a problem asks for an optimal choice step-by-step and local best choices always lead to global best, use greedy; if overlapping subproblems and optimal substructure exist but greedy fails, use DP.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution
Fix: Check problem properties; if greedy fails, implement DP to guarantee optimal

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

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 greedy fails.

The key is to test if greedy choice property holds; if not, DP is safer.