Greedy vs DP How to Know Which to Apply in DSA Go - Visual Comparison

Concept Flow - Greedy vs DP How to Know Which to Apply

Start Problem

↓

Check for Greedy Choice Property?

|Yes↓

Apply Greedy Algorithm

↓

Get Solution

No↓

Check for Overlapping Subproblems?

|Yes↓

Apply Dynamic Programming

↓

Get Solution

No↓

Problem may need other methods or backtracking

Decide if problem fits greedy choice property to use greedy; else if overlapping subproblems exist, use dynamic programming; otherwise, consider other methods.

Execution Sample

DSA Go

func solveProblem(input []int) int {
    if canUseGreedy(input) {
        return greedySolution(input)
    } else if hasOverlappingSubproblems(input) {
        return dpSolution(input)
    }
    return -1
}

This code chooses greedy or DP based on problem properties and returns the solution.

Execution Table

Step	Operation	Check/Action	Decision	Result/State
1	Start problem analysis	Input array received	N/A	Input: [3, 1, 4, 1, 5]
2	Check greedy choice property	Is local optimal choice always part of global optimal?	No	Greedy not applicable
3	Check overlapping subproblems	Do subproblems repeat?	Yes	DP applicable
4	Apply DP solution	Compute and store subproblem results	DP used	DP table filled with partial results
5	Return final solution	Use DP table to get answer	Solution found	Result = 7
6	End	No further steps	N/A	Final answer returned

💡 Execution stops after final solution is returned.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
input	[3,1,4,1,5]	[3,1,4,1,5]	[3,1,4,1,5]	[3,1,4,1,5]	[3,1,4,1,5]
canUseGreedy	undefined	false	false	false	false
hasOverlappingSubproblems	undefined	undefined	true	true	true
dpTable	empty	empty	empty	[partial results]	[complete results]
result	undefined	undefined	undefined	undefined	7

Key Moments - 3 Insights

Why can't we use greedy if local optimal choices don't lead to global optimal?

Because greedy algorithms rely on the greedy choice property, which means local optimal choices build the global solution. As shown in step 2 of execution_table, when this property is false, greedy fails.

What does overlapping subproblems mean and why is it important for DP?

Overlapping subproblems mean the problem can be broken into smaller subproblems that repeat. DP stores these results to avoid recomputation, as seen in step 3 and 4 where DP table is filled.

What if neither greedy nor DP applies?

If neither property holds, the problem may need other methods like backtracking or brute force, as indicated in the concept_flow after checks fail.

Visual Quiz - 3 Questions

Look at the execution_table, at which step do we decide greedy is not applicable?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Check the 'Decision' column in execution_table for when greedy is rejected.

According to variable_tracker, what is the value of hasOverlappingSubproblems after step 3?

A true

B undefined

C false

D empty

💡 Hint

Look at the 'hasOverlappingSubproblems' row under 'After Step 3' column.

If the problem had no overlapping subproblems, how would the execution_table change after step 3?

A DP would still be applied

B Greedy would be applied instead

C Execution would move to other methods or backtracking

D The problem would be solved immediately

💡 Hint

Refer to the concept_flow where no greedy and no overlapping subproblems leads to other methods.

Concept Snapshot

Greedy vs DP Decision Guide:
- Check if greedy choice property holds: local optima build global optima.
- If yes, use Greedy algorithm for fast solution.
- Else, check for overlapping subproblems.
- If yes, use Dynamic Programming to store and reuse results.
- Otherwise, consider other methods like backtracking.
- Always analyze problem properties before choosing approach.

Full Transcript

To decide between greedy and dynamic programming, first check if the problem has the greedy choice property, meaning local optimal choices lead to a global optimum. If yes, use greedy algorithms. If not, check if the problem has overlapping subproblems, where smaller parts repeat. If yes, use dynamic programming to store and reuse results. If neither applies, other methods like backtracking may be needed. This approach ensures efficient and correct solutions by matching problem properties to algorithm strategies.

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