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

Mental Model

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

Analogy: Imagine choosing snacks from a buffet: greedy grabs the tastiest snack first without thinking ahead, while DP plans the whole meal to get the tastiest combination.

Choices: [1] [2] [3] [4]
Greedy: picks -> [3] -> [4]
DP: explores all paths -> [1] -> [2] -> [3] -> [4]

Dry Run Walkthrough

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

Goal: Find the minimum number of coins to make 6 cents.

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

Chosen coins: 4 -> remaining 2

Why: Greedy tries to reduce amount quickly by picking largest coin.

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.

DP table: min coins for 0=0, 1=1, 2=2, 3=1, 4=1, 5=2, 6=2

Why: DP finds minimum coins by checking all possibilities.

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

Chosen coins: 3 -> 3 -> remaining 0

Why: DP finds better solution than greedy.

Result:

Greedy chosen coins: 4 -> 1 -> 1 -> null (3 coins)
DP chosen coins: 3 -> 3 -> null (2 coins)

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

type Result struct {
	coins []int
	count int
}

// GreedyCoinChange picks largest coin each time
func GreedyCoinChange(coins []int, amount int) Result {
	chosen := []int{}
	remaining := amount
	for remaining > 0 {
		maxCoin := 0
		for _, c := range coins {
			if c <= remaining && c > maxCoin {
				maxCoin = c
			}
		}
		if maxCoin == 0 {
			break // no coin fits
		}
		chosen = append(chosen, maxCoin)
		remaining -= maxCoin
	}
	return Result{coins: chosen, count: len(chosen)}
}

// DPMinCoins finds minimum coins using DP
func DPMinCoins(coins []int, amount int) Result {
	minCoins := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		minCoins[i] = math.MaxInt32
	}
	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if c <= i && minCoins[i-c] != math.MaxInt32 {
				if minCoins[i-c]+1 < minCoins[i] {
					minCoins[i] = minCoins[i-c] + 1
				}
			}
		}
	}
	// Reconstruct coins chosen
	chosen := []int{}
	rem := amount
	for rem > 0 {
		for _, c := range coins {
			if c <= rem && minCoins[rem-c] == minCoins[rem]-1 {
				chosen = append(chosen, c)
				rem -= c
				break
			}
		}
	}
	return Result{coins: chosen, count: minCoins[amount]}
}

func main() {
	coins := []int{1, 3, 4}
	amount := 6
	greedy := GreedyCoinChange(coins, amount)
	fmt.Print("Greedy chosen coins: ")
	for _, c := range greedy.coins {
		fmt.Printf("%d -> ", c)
	}
	fmt.Println("null (", greedy.count, "coins)")

	dp := DPMinCoins(coins, amount)
	fmt.Print("DP chosen coins: ")
	for _, c := range dp.coins {
		fmt.Printf("%d -> ", c)
	}
	fmt.Println("null (", dp.count, "coins)")
}

for remaining > 0 { ... }

pick largest coin possible repeatedly to reduce amount

for i := 1; i <= amount; i++ { ... }

build minCoins table bottom-up for all amounts

if minCoins[i-c]+1 < minCoins[i] { minCoins[i] = minCoins[i-c] + 1 }

update min coins for amount i if better found

for rem > 0 { ... }

reconstruct chosen coins from minCoins table

Output

Greedy chosen coins: 4 -> 1 -> 1 -> null ( 3 coins)

DP chosen coins: 3 -> 3 -> null ( 2 coins)

Complexity Analysis

Time: O(n*m) where n is amount and m is number of coins, because DP checks all amounts and coins; Greedy is O(n*m) worst case scanning coins each step.

Space: O(n) for DP table storing min coins for each amount; O(1) extra for greedy except output list.

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

Edge Cases

Amount zero

Both greedy and DP return zero coins chosen.

DSA Go

for remaining > 0 { ... } // greedy loop skips if amount zero

No coin fits amount

Greedy stops early with incomplete solution; DP returns MaxInt indicating no solution.

DSA Go

if maxCoin == 0 { break } // greedy stops if no coin fits

Single coin equals amount

Both greedy and DP pick that coin once.

DSA Go

if c <= i && minCoins[i-c] != math.MaxInt32 { ... } // DP updates minCoins

When to Use This Pattern

When a problem asks for optimal choices with overlapping subproblems, try DP; if local best choices always lead to global best, greedy works.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution.
Fix: Test with examples where greedy fails and use DP to confirm optimality.

Summary

Greedy picks the best immediate choice hoping for overall best; DP tries all choices and remembers results to guarantee best overall.

Use greedy when local best choices lead to global best; use DP when choices overlap and require exploring all options.

The key insight is that greedy is fast but sometimes wrong, while DP is slower but always correct by remembering past results.

Practice

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

easy

A. When the problem requires exploring all possible solutions

B. When the problem is unsolvable by any algorithm

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: Check 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 Go code snippet correctly declares a memoization map for dynamic programming?

easy

A. memo := new(map[int]int)

B. memo := make(map[int]int)

C. memo := map[]int{}

D. memo := []int{}

Solution

1. Step 1: Understand Go map declaration

   In Go, maps are declared with make(map[keyType]valueType) to initialize properly.

2. Step 2: Check each option

   memo := make(map[int]int) uses make with correct syntax. memo := []int{} is a slice, not a map. memo := map[]int{} has invalid syntax. memo := new(map[int]int) uses new which returns pointer, not initialized map.

3. Final Answer:

   memo := make(map[int]int) -> Option B

4. Quick Check:

   Use make(map[key]value) for maps [OK]

Hint: Use make(map[key]value) to create maps in Go [OK]

Common Mistakes:

• Using new(map[int]int) which returns nil map pointer
• Confusing slices with maps
• Incorrect map syntax like map[]int{}

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    weights := []int{1, 3, 4, 5}
    values := []int{1, 4, 5, 7}
    capacity := 7
    dp := make([]int, capacity+1)

    for i := 0; i < len(weights); i++ {
        for w := capacity; w >= weights[i]; w-- {
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
        }
    }
    fmt.Println(dp[capacity])
}

medium

A. 12

B. 10

C. 11

D. 9

Solution

1. Step 1: Understand the code - 0/1 Knapsack DP

   The code uses bottom-up DP to find max value for capacity 7 with given weights and values.

2. Step 2: Trace DP array updates

   Items: (1,1), (3,4), (4,5), (5,7). DP updates from capacity down to weight. Final dp[7] = max value achievable is 11.

3. Final Answer:

   11 -> Option C

4. Quick Check:

   DP knapsack max value = 11 [OK]

Hint: Trace DP from largest capacity down to weight [OK]

Common Mistakes:

• Iterating w from low to high causing wrong results
• Confusing weights and values arrays
• Forgetting to update dp[w] with max

4. Identify the bug in this greedy approach for coin change problem in Go:

func coinChange(coins []int, amount int) int {
    count := 0
    for _, coin := range coins {
        count += amount / coin
        amount %= coin
    }
    if amount != 0 {
        return -1
    }
    return count
}

func main() {
    coins := []int{1, 3, 4}
    amount := 6
    fmt.Println(coinChange(coins, amount))
}

medium

A. Coins slice is not sorted descending

B. Using integer division causes wrong count

C. No base case for amount zero

D. Returns -1 even if solution exists

Solution

1. Step 1: Analyze greedy coin change logic

   The greedy approach works only if coins are sorted descending to pick largest coin first.

2. Step 2: Check coins order

   Coins are {1,3,4} ascending, so greedy picks 1 first, leading to wrong minimal count.

3. Final Answer:

   Coins slice is not sorted descending -> Option A

4. Quick Check:

   Sort coins descending for greedy coin change [OK]

Hint: Sort coins descending before greedy coin change [OK]

Common Mistakes:

• Not sorting coins descending
• Assuming greedy always works for coin change
• Ignoring leftover amount check

5. You want to find the minimum number of coins to make amount 11 using coins {1, 5, 6}. Which approach is best and why?

hard

A. Dynamic Programming, because greedy fails due to no greedy choice property

B. Greedy, because coins are sorted ascending

C. Greedy, because picking largest coin first always works

D. Neither, because problem is unsolvable

Solution

1. Step 1: Check greedy choice property for coin set

   For coins {1,5,6}, greedy picks 6 then 5, total 2 coins for 11, which is minimal. However, greedy does not always work for all amounts with these coins.

2. Step 2: Consider counterexamples and DP suitability

   In some cases greedy fails (e.g., amount 7 with coins {1,5,6} greedy picks 6+1=2 coins but better is 1+1+5=3 coins, so greedy works here but not always. DP always finds minimal coins by exploring all subproblems.

3. Final Answer:

   Dynamic Programming, because greedy fails due to no greedy choice property -> Option A

4. Quick Check:

   Use DP if greedy choice property missing [OK]

Hint: Use DP if greedy choice property is missing [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring overlapping subproblems in coin change
• Choosing greedy because coins are sorted ascending