DP vs Recursion vs Greedy Choosing the Right Tool in DSA Go - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: You are helping a small delivery company decide the best way to calculate the minimum cost to deliver packages along a route. They want to understand three different approaches: simple recursion, greedy choice, and dynamic programming.Each package has a delivery cost, and the company wants to find the minimum total cost to deliver all packages in order.

🎯 Goal: Build three functions in Go to calculate the minimum delivery cost using recursion, greedy, and dynamic programming. Compare their outputs to see which method works best.

📋 What You'll Learn

Create a slice called costs with the exact values: 3, 2, 7, 10

Create an integer variable called n and set it to the length of costs

Write a recursive function called minCostRecursion that takes costs and n and returns the minimum cost

Write a greedy function called minCostGreedy that takes costs and returns the minimum cost by choosing the cheapest package first

Write a dynamic programming function called minCostDP that takes costs and n and returns the minimum cost using bottom-up approach

Print the results of all three functions with clear labels

💡 Why This Matters

🌍 Real World

Delivery companies often need to find the cheapest way to deliver packages. Understanding different algorithm approaches helps choose the best method for cost and speed.

💼 Career

Knowing recursion, greedy, and dynamic programming is essential for software engineers solving optimization problems in logistics, finance, and many other fields.

1

Create the delivery costs data

Create a slice called costs with the exact values 3, 2, 7, 10.

DSA Go

# Create the costs slice with values 3, 2, 7, 10
// Your code here

Hint

Use costs := []int{3, 2, 7, 10} to create the slice.

2

Set the length variable

Create an integer variable called n and set it to the length of costs.

DSA Go

package main

func main() {
    costs := []int{3, 2, 7, 10}
    // Set n to length of costs
    // Your code here
}

Hint

Use len(costs) to get the length.

3

Write the recursive function

Write a recursive function called minCostRecursion that takes costs and n and returns the minimum cost to deliver all packages up to n. Use the base case when n is 0 or 1.

DSA Go

package main

func minCostRecursion(costs []int, n int) int {
    // Your code here
}

func main() {
    costs := []int{3, 2, 7, 10}
    n := len(costs)
}

Hint

Use recursion with base cases for n <= 0 and n == 1. Compare two recursive calls for n-1 and n-2.

4

Write greedy and DP functions and print results

Write a greedy function called minCostGreedy that takes costs and returns the minimum cost by always choosing the cheapest package first. Write a dynamic programming function called minCostDP that takes costs and n and returns the minimum cost using bottom-up approach. Then print the results of minCostRecursion(costs, n), minCostGreedy(costs), and minCostDP(costs, n) with labels.

DSA Go

package main

func minCostRecursion(costs []int, n int) int {
    if n <= 0 {
        return 0
    } else if n == 1 {
        return costs[0]
    }
    cost1 := minCostRecursion(costs, n-1) + costs[n-1]
    cost2 := minCostRecursion(costs, n-2) + costs[n-2]
    if cost1 < cost2 {
        return cost1
    }
    return cost2
}

// Write minCostGreedy function here
// Write minCostDP function here

func main() {
    costs := []int{3, 2, 7, 10}
    n := len(costs)
    // Print results of all three functions
    // Your code here
}

Hint

For greedy, pick the cheapest package each time and sum costs. For DP, build a dp array with minimum costs up to each package. Print all results with labels.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems means the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller parts.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization
• Confusing brute force with DP

2. Which of the following Go function signatures correctly represents a recursive function to compute factorial?

easy

A. func factorial(n int) { if n == 0 { return 1 } return n * factorial(n-1) }

B. func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) }

C. func factorial(n int) int { if n == 0 { return 0 } return n * factorial(n-1) }

D. func factorial(n int) int { if n == 1 { return 0 } return n * factorial(n-1) }

Solution

1. Step 1: Check function return type and base case

   Factorial returns int, so function must return int. Base case for factorial is n == 0 returning 1.

2. Step 2: Verify recursive call and return statement

   Recursive call multiplies n by factorial(n-1). func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } matches correct signature and logic.

3. Final Answer:

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } -> Option B

4. Quick Check:

   Correct return type and base case = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Check base case and return type carefully in recursion [OK]

Common Mistakes:

• Missing return type in function signature
• Incorrect base case value
• Returning wrong type or no return

3. What is the output of this Go code using recursion to compute Fibonacci numbers?

func fib(n int) int {
  if n <= 1 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  fmt.Println(fib(5))
}

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3); fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0)

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1; fib(2)=1; fib(3)=2; fib(4)=3; fib(5)=5

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5,8... [OK]

Common Mistakes:

• Confusing index starting point
• Miscomputing recursive calls
• Assuming fib(1) = 0

4. Identify the error in this greedy algorithm code snippet for coin change in Go:

func coinChange(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
}

medium

A. Greedy may fail if coins are not canonical denominations

B. The inner loop should increment amount instead of decrement

C. Coins array must be sorted in ascending order

D. Return value should be amount instead of count

Solution

1. Step 1: Understand greedy coin change logic

   The code tries largest coins first, subtracting from amount until no longer possible.

2. Step 2: Identify limitation of greedy approach

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it may not find minimum coins or any solution.

3. Final Answer:

   Greedy may fail if coins are not canonical denominations -> Option A

4. Quick Check:

   Greedy correctness depends on coin set [OK]

Hint: Greedy coin change fails on non-standard coin sets [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Misunderstanding return values

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why? A) Simple recursion tries all subsequences but is slow. B) Greedy picks local best but may miss global LIS. C) Dynamic Programming stores LIS lengths to avoid recomputation. D) Brute force enumerates all subsequences without optimization.

hard

A. Simple recursion is best for LIS

B. Greedy approach always finds LIS

C. Brute force is efficient for LIS

D. Dynamic Programming is best for LIS

Solution

1. Step 1: Analyze LIS problem nature

   LIS requires checking subsequences and their lengths. Simple recursion tries all but is exponential time.

2. Step 2: Compare approaches

   Greedy fails because local choices don't guarantee global LIS. DP stores LIS lengths for subproblems, improving efficiency.

3. Final Answer:

   Dynamic Programming is best for LIS -> Option D

4. Quick Check:

   LIS problem = DP best approach [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Choosing greedy for LIS
• Ignoring exponential time of recursion
• Thinking brute force is efficient