Greedy vs DP How to Know Which to Apply in DSA Go - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Choose Greedy Over Dynamic Programming?

Which condition best indicates that a greedy algorithm is suitable instead of dynamic programming?

A The problem has overlapping subproblems and optimal substructure.

B The problem has optimal substructure but no overlapping subproblems.

C The problem requires exploring all possible combinations to find the best solution.

D The problem has neither optimal substructure nor overlapping subproblems.

💡 Hint

Think about when greedy algorithms can make decisions step-by-step without revisiting previous choices.

Greedy algorithms work well when the problem has optimal substructure but no overlapping subproblems, allowing local choices to lead to a global optimum without revisiting states.

❓ Predict Output

intermediate

Output of Greedy vs DP Coin Change

What is the output of the following Go code that tries to find the minimum coins for amount 6 using coins [1, 3, 4]?

DSA Go

package main
import "fmt"
func greedyCoinChange(coins []int, amount int) int {
    count := 0
    for i := len(coins) - 1; i >= 0; i-- {
        for amount >= coins[i] {
            amount -= coins[i]
            count++
        }
    }
    if amount != 0 {
        return -1
    }
    return count
}
func main() {
    coins := []int{1, 3, 4}
    amount := 6
    fmt.Println(greedyCoinChange(coins, amount))
}

A 3

B 2

C -1

D 4

💡 Hint

Trace how the greedy picks coins starting from the largest coin.

The greedy picks 4 once (amount=2 left), then picks 1 twice, total 3 coins. But the optimal solution is 2 coins (3+3). Greedy returns 3 here.

❓ Predict Output

advanced

Dynamic Programming Coin Change Minimum Coins Output

What is the output of this Go code that uses dynamic programming to find minimum coins for amount 6 with coins [1, 3, 4]?

DSA Go

package main
import "fmt"
import "math"
func dpCoinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt32
        for _, c := range coins {
            if i-c >= 0 && dp[i-c] != math.MaxInt32 {
                if dp[i-c]+1 < dp[i] {
                    dp[i] = dp[i-c] + 1
                }
            }
        }
    }
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}
func main() {
    coins := []int{1, 3, 4}
    amount := 6
    fmt.Println(dpCoinChange(coins, amount))
}

A 4

B 3

C -1

D 2

💡 Hint

Dynamic programming tries all combinations to find the minimum coins.

The DP finds the minimum coins as 2 (3 + 3) which is better than greedy's 3 coins.

🔧 Debug

advanced

Identify the Error in Greedy Algorithm for Activity Selection

What error does the following Go code produce when trying to select maximum activities using a greedy approach?

DSA Go

package main
import "fmt"
type Activity struct {
    start, end int
}
func maxActivities(activities []Activity) int {
    count := 1
    prevEnd := activities[0].end
    for i := 1; i < len(activities); i++ {
        if activities[i].start > prevEnd {
            count++
            prevEnd = activities[i].end
        }
    }
    return count
}
func main() {
    acts := []Activity{{1,3},{2,5},{4,7},{6,9}}
    fmt.Println(maxActivities(acts))
}

A 3

B 0

C runtime error: index out of range

D 4

💡 Hint

Check if the activities are sorted correctly before applying greedy.

The code assumes activities are sorted by end time but they are not, so the greedy picks suboptimal activities. The output is 3.

🧠 Conceptual

expert

Why Dynamic Programming is Needed Over Greedy in Some Problems?

Which reason best explains why dynamic programming is necessary instead of greedy algorithms for some problems?

A Because the problem has optimal substructure but no overlapping subproblems.

B Because greedy algorithms always produce the worst solution.

C Because the problem has overlapping subproblems and greedy choices do not guarantee global optimum.

D Because dynamic programming is faster than greedy algorithms in all cases.

💡 Hint

Think about when greedy local choices fail to find the best overall solution.

Dynamic programming is needed when problems have overlapping subproblems and greedy choices can lead to suboptimal solutions, requiring exploration of all subproblems.

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