Overlapping Subproblems and Optimal Substructure in DSA C - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Problem

→Break into subproblems

↓

Check if subproblem solved?

Yes→Use stored solution

No↓

Compute subproblem

↓

Store solution

↓

Combine subproblems for final answer

The problem is divided into smaller subproblems. If a subproblem was solved before, reuse its answer. Otherwise, solve it, store the result, and combine all to get the final solution.

Execution Sample

DSA C

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

This code calculates Fibonacci numbers using recursion, showing overlapping subproblems as fib(n-1) and fib(n-2) are computed multiple times.

Execution Table

Step	Operation	Subproblem Computed	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	Return fib(1) = 1	fib(1)	{fib(1)=1}	Store fib(1)=1
6	Call fib(0)	fib(0)	{fib(1)=1}	fib(0) base case returns 0
7	Return fib(0) = 0	fib(0)	{fib(1)=1, fib(0)=0}	Store fib(0)=0
8	Return fib(2) = 1	fib(2)	{fib(1)=1, fib(0)=0}	fib(2) = fib(1)+fib(0) = 1+0=1
9	Call fib(1)	fib(1)	{fib(1)=1, fib(0)=0}	fib(1) found in stored solutions, reuse 1
10	Return fib(3) = 2	fib(3)	{fib(1)=1, fib(0)=0, fib(2)=1}	fib(3) = fib(2)+fib(1) = 1+1=2
11	Call fib(2)	fib(2)	{fib(1)=1, fib(0)=0, fib(2)=1}	fib(2) found in stored solutions, reuse 1
12	Return fib(4) = 3	fib(4)	{fib(1)=1, fib(0)=0, fib(2)=1, fib(3)=2}	fib(4) = fib(3)+fib(2) = 2+1=3
13	End	-	{fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3}	Final result fib(4)=3

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

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 8	After Step 10	After Step 12	Final
fib(0)	undefined	undefined	0	0	0	0	0
fib(1)	undefined	1	1	1	1	1	1
fib(2)	undefined	undefined	undefined	1	1	1	1
fib(3)	undefined	undefined	undefined	undefined	2	2	2
fib(4)	undefined	undefined	undefined	undefined	undefined	3	3

Key Moments - 3 Insights

Why do we compute fib(2) multiple times in the naive recursion?

Because fib(2) is called separately from fib(3) and fib(4) without storing its result, as seen in steps 3 and 11. This shows overlapping subproblems.

How does storing solutions help avoid repeated work?

Stored solutions like fib(1)=1 and fib(0)=0 are reused in steps 9 and 11, preventing recomputation and saving time.

What does optimal substructure mean in this example?

The solution to fib(4) depends on solutions to fib(3) and fib(2), which are smaller subproblems. Combining these gives the optimal answer, as shown in step 12.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of fib(2) after step 8?

A 2

B 0

C 1

D Undefined

💡 Hint

Check the 'Stored Solutions' column at step 8 where fib(2) is computed as 1.

At which step does the recursion reuse a stored solution for fib(1)?

A Step 4

B Step 9

C Step 6

D Step 12

💡 Hint

Look for when fib(1) is found in stored solutions instead of recomputed.

If we add memoization to the code, how would the number of fib(2) computations change?

A It would reduce to one

B It would stay the same

C It would increase

D It would become zero

💡 Hint

Refer to variable_tracker and execution_table showing repeated fib(2) calls without memoization.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Reuse solutions of repeated subproblems (memoization)
- Combine subproblem solutions for final answer
- Enables efficient dynamic programming
- Example: Fibonacci numbers computed once each

Full Transcript

This concept shows how some problems can be split into smaller parts that repeat. Instead of solving the same part many times, we save the answer once and reuse it. This saves time and makes the solution faster. The Fibonacci example shows how fib(2) is computed multiple times without saving, but with storing results, each subproblem is solved once. The problem also has optimal substructure, meaning the final answer is made by combining answers of smaller parts. This is the base of dynamic programming.