Overlapping Subproblems and Optimal Substructure in DSA Go - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Start Problem

↓

Check if solution known?

Yes→Return stored solution

No↓

Break problem into subproblems

↓

Recursively solve subproblems

↓

Combine subproblem solutions

↓

Store solution for reuse

↓

Return solution

↓

End

This flow shows how a problem is solved by breaking it into smaller parts, reusing answers to repeated parts, and combining them to get the final answer.

Execution Sample

DSA Go

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

This code calculates Fibonacci numbers using recursion, showing overlapping subproblems and optimal substructure.

Execution Table

Step	Operation	Subproblem	Stored Solutions	Visual State
1	Call fib(4)	fib(4)	{}	fib(4) called, no stored solutions
2	Call fib(3)	fib(3)	{}	fib(3) called inside fib(4)
3	Call fib(2)	fib(2)	{}	fib(2) called inside fib(3)
4	Call fib(1)	fib(1)	{}	fib(1) base case returns 1
5	Call fib(0)	fib(0)	{}	fib(0) base case returns 0
6	Calculate fib(2)	fib(2)	{fib(1)=1, fib(0)=0}	fib(2) = 1 + 0 = 1 stored
7	Call fib(1)	fib(1)	{fib(2)=1}	fib(1) base case returns 1
8	Calculate fib(3)	fib(3)	{fib(2)=1, fib(1)=1}	fib(3) = 1 + 1 = 2 stored
9	Call fib(2)	fib(2)	{fib(3)=2, fib(2)=1, fib(1)=1}	fib(2) found in stored solutions, reuse 1
10	Calculate fib(4)	fib(4)	{fib(3)=2, fib(2)=1, fib(1)=1}	fib(4) = 2 + 1 = 3 stored
11	Return fib(4)	fib(4)	{fib(4)=3, fib(3)=2, fib(2)=1, fib(1)=1}	Final result 3 returned
12	End	-	{fib(4)=3, fib(3)=2, fib(2)=1, fib(1)=1}	All subproblems solved and stored

💡 fib(4) computed using stored subproblems, recursion ends

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
fib(4)	not computed	not computed	not computed	3	3
fib(3)	not computed	not computed	2	2	2
fib(2)	not computed	1	1	1	1
fib(1)	not computed	1	1	1	1
fib(0)	not computed	0	0	0	0
Stored Solutions	{}	{fib(1)=1, fib(0)=0}	{fib(2)=1, fib(1)=1}	{fib(3)=2, fib(2)=1, fib(1)=1}	{fib(4)=3, fib(3)=2, fib(2)=1, fib(1)=1}

Key Moments - 3 Insights

Why do we call fib(2) twice in the recursion?

fib(2) is called twice because the recursive calls overlap. The first call computes fib(2) and stores it (see step 6). The second call (step 9) finds fib(2) already stored and reuses it, avoiding repeated work.

What does 'optimal substructure' mean here?

It means the solution to fib(4) can be built from solutions to fib(3) and fib(2). Each smaller problem's answer helps build the bigger problem's answer (see steps 8 and 10).

Why do we store solutions after computing them?

Storing solutions (memoization) avoids recalculating the same subproblems multiple times, saving time and making the algorithm efficient (see stored solutions column in steps 6, 8, 10).

Visual Quiz - 3 Questions

Look at the execution table at step 9, what happens when fib(2) is called?

A fib(2) is computed again from scratch

B fib(2) returns 0

C fib(2) is found in stored solutions and reused

D fib(2) causes an error

💡 Hint

Check the 'Stored Solutions' and 'Visual State' columns at step 9 in the execution table

At which step is fib(3) first stored in the solutions?

A Step 8

B Step 6

C Step 10

D Step 4

💡 Hint

Look at the 'Stored Solutions' column and 'Operation' at each step in the execution table

If we did not store solutions, how would the execution table change?

A The final result would be different

B More repeated calls to the same subproblems would appear

C Fewer steps would be needed

D The recursion would stop earlier

💡 Hint

Think about the purpose of storing solutions shown in the 'Stored Solutions' column

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Subproblems overlap and repeat
- Store solutions to reuse (memoization)
- Combine subproblem solutions for final answer
- Enables efficient recursive algorithms like Fibonacci

Full Transcript

This concept shows how some problems can be broken into smaller parts that repeat. We solve each small part once and save the answer. Later, if the same part is needed, we reuse the saved answer instead of solving again. This saves time and makes the solution faster. The example is the Fibonacci sequence, where fib(4) depends on fib(3) and fib(2). We see fib(2) called twice but computed once and reused. This is called overlapping subproblems. Also, the problem has optimal substructure because the big problem's answer is made from smaller answers. Storing answers is called memoization. This approach is key to dynamic programming.

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