Overlapping Subproblems and Optimal Substructure in DSA Python - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Start Problem

↓

Check if solution known?

Yes→Return stored solution

No↓

Divide problem into subproblems

↓

Recursively solve subproblems

↓

Combine subproblem solutions

↓

Store solution for reuse

↓

Return solution

↓

End

This flow shows how a problem is broken into smaller parts, solved recursively, and solutions are saved to avoid repeated work.

Execution Sample

DSA Python

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Calculates Fibonacci numbers using memoization to reuse solutions of overlapping subproblems.

Execution Table

Step	Operation	Current n	Memo Before	Memo After	Returned Value	Visual State
1	Call fib(4)	4	{}	{4: ?}	?	fib(4) called, memo empty
2	Call fib(3)	3	{}	{3: ?}	?	fib(3) called inside fib(4)
3	Call fib(2)	2	{}	{2: ?}	?	fib(2) called inside fib(3)
4	Call fib(1)	1	{}	{}	1	fib(1) base case returns 1
5	Call fib(0)	0	{}	{}	0	fib(0) base case returns 0
6	Compute fib(2)	2	{}	{2:1}	1	fib(2) = fib(1)+fib(0) = 1+0=1 stored
7	Call fib(1)	1	{2:1}	{2:1}	1	fib(1) base case returns 1
8	Compute fib(3)	3	{2:1}	{2:1, 3:2}	2	fib(3) = fib(2)+fib(1) = 1+1=2 stored
9	Call fib(2)	2	{2:1, 3:2}	{2:1, 3:2}	1	fib(2) found in memo, returns 1
10	Compute fib(4)	4	{2:1, 3:2}	{2:1, 3:2, 4:3}	3	fib(4) = fib(3)+fib(2) = 2+1=3 stored
11	Return fib(4)	4	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}	3	Final result returned
12	End	-	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}	3	Execution complete

💡 fib(4) computed using memoized results, recursion ends when base cases reached

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 10	Final
n	4	1	2	3	4	4
memo	{}	{}	{2:1}	{2:1, 3:2}	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}
Returned Value	-	1	1	2	3	3

Key Moments - 3 Insights

Why does fib(2) get computed only once and reused later?

Because after fib(2) is computed at step 6, its result is stored in memo. Later at step 9, fib(2) is found in memo and returned directly without recomputation.

What stops the recursion from going infinitely?

The base cases at steps 4 and 5 return values directly for n=1 and n=0, preventing further recursive calls.

Why do we check 'if n in memo' at the start?

To reuse already computed results and avoid repeating the same calculations, as seen at step 9 where fib(2) is returned from memo.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo after step 8?

A {2:1}

B {}

C {2:1, 3:2}

D {2:1, 3:2, 4:3}

💡 Hint

Check the 'Memo After' column at step 8 in the execution table.

At which step does the recursion hit the base case for n=0?

A Step 5

B Step 4

C Step 6

D Step 9

💡 Hint

Look for the step where 'Current n' is 0 and a base case return happens.

If we remove the memo dictionary, how would the execution table change?

A Returned values would be incorrect

B More repeated calls for the same n values would appear

C Memo would store more values

D Base cases would not be reached

💡 Hint

Think about how memoization avoids repeated calculations shown in the table.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Solve subproblems recursively
- Store solutions (memoization) to reuse (overlapping subproblems)
- Combine subproblem solutions for final answer
- Enables efficient dynamic programming solutions

Full Transcript

This concept shows how some problems can be split into smaller parts that overlap. Instead of solving the same part many times, we save the answer once and reuse it. For example, the Fibonacci sequence calculation uses memoization to store results of smaller Fibonacci numbers. The flow starts by checking if the answer is already known. If yes, it returns it immediately. If not, it breaks the problem down, solves smaller parts, stores the result, and returns it. This avoids repeated work and speeds up the solution. The execution table traces each step of the Fibonacci function calls, showing how memo grows and how results are returned. Key moments include understanding why memoization avoids repeated calculations and how base cases stop recursion. The visual quiz tests understanding of memo state, base cases, and the effect of removing memoization. This concept is the foundation of dynamic programming, making complex problems manageable by reusing solutions of overlapping subproblems.

Practice

1. Which of the following best describes the overlapping subproblems property in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems that are reused multiple times.

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

C. The problem requires sorting before solving.

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 solving.

2. Step 2: Match definition to options

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

3. Final Answer:

   The problem can be broken down into smaller subproblems that are reused multiple times. -> Option A

4. Quick Check:

   Overlapping subproblems = reuse of subproblems [OK]

Hint: Look for repeated smaller problems in the main problem [OK]

Common Mistakes:

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

2. Which of the following Python function definitions correctly uses memoization to solve overlapping subproblems?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): return n * fib(n-1)

C. def fib(n): for i in range(n): print(i)

D. def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]

Solution

1. Step 1: Identify memoization usage

   Memoization stores results of subproblems to avoid repeated work, usually with a dictionary.

2. Step 2: Check each option

   def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] uses a dictionary 'memo' to save and reuse results, correctly implementing memoization.

3. Final Answer:

   def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] -> Option D

4. Quick Check:

   Memoization = caching results [OK]

Hint: Look for a cache (dictionary) storing computed results [OK]

Common Mistakes:

• Missing memo dictionary parameter
• Not returning cached results
• Using loops without caching results

3. What is the output of the following code?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 13

B. 8

C. 5

D. 3

Solution

1. Step 1: Trace fib(5) calls with memoization

   fib(5) calls fib(4) and fib(3), which further call smaller fib values, caching 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 C

4. Quick Check:

   Fibonacci(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
• Miscounting base cases

4. The following code attempts to use memoization for Fibonacci numbers but has a bug. What is the error?

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(4))

medium

A. Missing memo argument in recursive calls causes infinite recursion.

B. Base case is incorrect for n <= 1.

C. Memo dictionary is not initialized.

D. Return statement is missing.

Solution

1. Step 1: Check recursive calls

   Recursive calls fib(n-1) and fib(n-2) do not pass 'memo', so memo is empty each time.

2. Step 2: Understand effect of missing memo argument

   Without passing memo, caching fails and recursion repeats infinitely, causing a stack overflow.

3. Final Answer:

   Missing memo argument in recursive calls causes infinite recursion. -> Option A

4. Quick Check:

   Pass memo in recursive calls to fix [OK]

Hint: Always pass memo/cache in recursive calls [OK]

Common Mistakes:

• Forgetting to pass memo in recursive calls
• Assuming base case alone stops recursion
• Not initializing memo outside function

5. You want to find the minimum cost to reach the top of stairs where each step has a cost. You can climb 1 or 2 steps at a time. Which approach best uses optimal substructure and overlapping subproblems to solve this?

hard

A. Use recursion without caching to try all paths.

B. Use dynamic programming to store minimum cost for each step and build up solution.

C. Sort the costs and pick the smallest steps first.

D. Use a greedy approach to always pick the next step with minimum cost.

Solution

1. Step 1: Understand problem structure

   Minimum cost to reach step i depends on minimum cost to reach steps i-1 and i-2 plus cost at i.

2. Step 2: Apply dynamic programming

   Store minimum costs for each step to avoid recomputing (overlapping subproblems) and use previous results (optimal substructure).

3. Final Answer:

   Use dynamic programming to store minimum cost for each step and build up solution. -> Option B

4. Quick Check:

   DP uses optimal substructure + overlapping subproblems [OK]

Hint: Build solution step-by-step storing results [OK]

Common Mistakes:

• Using recursion without memoization causing slow solution
• Trying greedy approach which may fail
• Sorting costs which is irrelevant