Overlapping Subproblems and Optimal Substructure in DSA Go

Mental Model

Some problems can be broken into smaller parts that repeat, and the best solution uses the best answers to those parts.

Analogy: Imagine building a big Lego castle by reusing the same small Lego pieces many times instead of making new ones each time.

Problem
  ↓
Subproblem A -> Subproblem B -> Subproblem C
  ↓           ↓
Subproblem A (reused)  Subproblem B (reused)

Dry Run Walkthrough

Input: Calculate Fibonacci number for 5 using overlapping subproblems and optimal substructure

Goal: Show how smaller Fibonacci numbers are reused to build the answer efficiently

Step 1: Calculate Fib(5) by breaking into Fib(4) + Fib(3)

Fib(5) = Fib(4) + Fib(3)

Why: We split the problem into smaller parts to solve step by step

Step 2: Calculate Fib(4) by Fib(3) + Fib(2)

Fib(5) = (Fib(3) + Fib(2)) + Fib(3)

Why: Fib(4) also breaks down into smaller Fibonacci numbers

Step 3: Calculate Fib(3) by Fib(2) + Fib(1)

Fib(5) = ((Fib(2) + Fib(1)) + Fib(2)) + Fib(3)

Why: We continue breaking down until base cases

Step 4: Calculate Fib(2) by Fib(1) + Fib(0)

Fib(5) = (((Fib(1) + Fib(0)) + Fib(1)) + Fib(2)) + Fib(3)

Why: Base cases Fib(1)=1 and Fib(0)=0 will stop recursion

Step 5: Reuse Fib(3) calculated earlier instead of recalculating

Fib(5) = ((Fib(3) + Fib(2)) + Fib(3)) with Fib(3) known

Why: Overlapping subproblems means we reuse answers to save work

Step 6: Combine all known values to get Fib(5) = 5

Fib(5) = 5

Why: Optimal substructure means the best answer uses best smaller answers

Result:

Fib(5) = 5

Annotated Code

DSA Go

package main

import "fmt"

// fibMemo stores previously calculated Fibonacci numbers
var fibMemo = map[int]int{}

// fib calculates Fibonacci number using memoization
func fib(n int) int {
    if n <= 1 {
        return n // base case
    }
    if val, found := fibMemo[n]; found {
        return val // reuse stored result
    }
    // calculate fib(n-1) and fib(n-2) recursively
    result := fib(n-1) + fib(n-2)
    fibMemo[n] = result // store result for reuse
    return result
}

func main() {
    n := 5
    fmt.Printf("Fib(%d) = %d\n", n, fib(n))
}

if n <= 1 { return n }

return base case values 0 or 1 to stop recursion

if val, found := fibMemo[n]; found { return val }

reuse previously calculated Fibonacci number to avoid repeated work

result := fib(n-1) + fib(n-2)

break problem into smaller subproblems and combine their results

fibMemo[n] = result

store result for future reuse to exploit overlapping subproblems

Output

Fib(5) = 5

Complexity Analysis

Time: O(n) because each Fibonacci number from 0 to n is calculated once and reused

Space: O(n) for the memoization map storing results for each subproblem

vs Alternative: Naive recursion is O(2^n) due to repeated calculations; memoization reduces it to O(n)

Edge Cases

n = 0 or n = 1

Returns n immediately as base case without recursion

DSA Go

if n <= 1 { return n }

Repeated calls with same n

Returns stored result from memo map without recalculating

DSA Go

if val, found := fibMemo[n]; found { return val }

When to Use This Pattern

When a problem can be split into smaller repeated parts and the best solution uses best answers to those parts, look for overlapping subproblems and optimal substructure patterns.

Common Mistakes

Mistake: Not storing results of subproblems causing repeated calculations
Fix: Use a memoization map or array to save and reuse results

Mistake: Missing base cases leading to infinite recursion
Fix: Always define and return base cases like fib(0)=0 and fib(1)=1

Summary

It breaks problems into smaller parts that repeat and uses best answers to those parts to build the final solution.

Use it when a problem can be divided into overlapping smaller problems with optimal solutions.

The key is to store and reuse answers to repeated subproblems to avoid extra work.

Practice

1. Which of the following best describes the Overlapping Subproblems property in dynamic programming?

easy

A. The problem requires sorting before solving.

B. The problem has a unique solution without repeating any subproblems.

C. The problem can be broken down into smaller subproblems which are solved multiple times.

D. The problem can only be solved using recursion without memoization.

Solution

1. Step 1: Understand Overlapping Subproblems

   Overlapping subproblems means the same smaller problems appear multiple times during the solution process.

2. Step 2: Match the definition with options

   The problem can be broken down into smaller subproblems which are solved multiple times. correctly states that subproblems are solved multiple times, which is the key idea behind overlapping subproblems.

3. Final Answer:

   The problem can be broken down into smaller subproblems which are solved multiple times. -> Option C

4. Quick Check:

   Overlapping Subproblems = repeated smaller problems [OK]

Hint: Look for repeated smaller problems solved multiple times [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking sorting is required for overlapping subproblems
• Assuming recursion alone solves overlapping subproblems

2. Which Go code snippet correctly declares a memoization map for storing integer results keyed by integer inputs?

easy

A. memo := make([]int, 10)

B. memo := map[string]int{}

C. memo := []int{}

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

Solution

1. Step 1: Identify correct map declaration for memoization

   Memoization requires a map with keys and values. Here keys and values are integers.

2. Step 2: Check each option

   memo := make(map[int]int) uses make(map[int]int) which creates a map with int keys and int values, perfect for memoization.

3. Final Answer:

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

4. Quick Check:

   Map[int]int for memoization = memo := make(map[int]int) [OK]

Hint: Use make(map[int]int) for int-to-int memo maps [OK]

Common Mistakes:

• Using slices instead of maps for memoization
• Using wrong key types like string when int is needed
• Confusing slice initialization with map initialization

3. What is the output of the following Go code implementing Fibonacci with memoization?

package main
import "fmt"

func fib(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int)
    fmt.Println(fib(5, memo))
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation with memo

   fib(5) = fib(4) + fib(3), and so on, with memo storing results to avoid repeats.

2. Step 2: Calculate fib(5)

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

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect and recalculating
• Mixing up base cases n<=1

4. Identify the bug in this Go code snippet for memoized Fibonacci:

func fib(n int, memo map[int]int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

medium

A. Memo map is not initialized before use

B. Base case should be n <= 1 instead of separate checks

C. Base case for n == 0 is missing

D. Function does not return memo[n] after calculation

Solution

1. Step 1: Check base cases and memo usage

   Base cases for n==0 and n==1 are correctly handled. Memo is used properly inside function.

2. Step 2: Identify initialization issue

   The function expects memo map passed in, but if not initialized before calling, it causes runtime error.

3. Final Answer:

   Memo map is not initialized before use -> Option A

4. Quick Check:

   Uninitialized map causes runtime panic [OK]

Hint: Always initialize maps before passing to functions [OK]

Common Mistakes:

• Assuming base cases are wrong when they are correct
• Forgetting to initialize memo map before first call
• Missing return statement after memo assignment

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. The cost grid is:

cost := [][]int{
  {1, 3, 5},
  {2, 1, 2},
  {4, 3, 1},
}

Which approach best uses Overlapping Subproblems and Optimal Substructure to solve this efficiently?

hard

A. Use recursion without memoization to explore all paths

B. Use dynamic programming with a 2D memo table storing minimum cost to each cell

C. Sort the grid and pick the smallest costs in order

D. Use a greedy approach picking the smallest cost neighbor at each step

Solution

1. Step 1: Understand problem properties

   Minimum cost path has optimal substructure: minimum cost to a cell depends on minimum cost to neighbors.

2. Step 2: Choose approach using overlapping subproblems

   Dynamic programming with a 2D memo table stores results of subproblems (cells), avoiding repeated calculations.

3. Final Answer:

   Use dynamic programming with a 2D memo table storing minimum cost to each cell -> Option B

4. Quick Check:

   DP with memo table = efficient solution [OK]

Hint: Use DP table to store subproblem results for grid paths [OK]

Common Mistakes:

• Trying recursion without memo causes exponential time
• Sorting grid ignores path constraints
• Greedy approach may miss global minimum path