Overlapping Subproblems and Optimal Substructure in DSA Typescript - 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

The problem is broken into smaller parts. If a part was solved before, reuse it. Otherwise, solve it and save the answer for later.

Execution Sample

DSA Typescript

function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[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	n	memo State	Action	Returned Value
1	fib(4) called	4	[]	Check base case and memo	—
2	fib(3) called	3	[]	Check base case and memo	—
3	fib(2) called	2	[]	Check base case and memo	—
4	fib(1) called	1	[]	Base case n<=1, return 1	1
5	fib(0) called	0	[]	Base case n<=1, return 0	0
6	fib(2) memoize	2	[undefined, 1]	Store fib(2)=1	1
7	fib(1) called	1	[undefined, 1]	Base case n<=1, return 1	1
8	fib(3) memoize	3	[undefined, 1, 2]	Store fib(3)=2	2
9	fib(2) called	2	[undefined, 1, 2]	Return memoized fib(2)=1	1
10	fib(4) memoize	4	[undefined, 1, 2, 3]	Store fib(4)=3	3
11	Return fib(4)	4	[undefined, 1, 2, 3]	Final result	3

💡 fib(4) returns 3 after reusing memoized results for fib(2) and fib(3)

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	[]	[]	[undefined, 1]	[undefined, 1, 2]	[undefined, 1, 2, 3]	[undefined, 1, 2, 3]
Returned Value	—	1	1	2	3	3

Key Moments - 3 Insights

Why do we check if memo[n] is defined before computing fib(n)?

Because fib(n) might have been computed before (see Step 9), so we reuse the stored result to avoid repeated work.

Why do we store the result in memo before returning it?

Storing the result (Step 6, 8, 10) allows future calls to reuse the solution, demonstrating overlapping subproblems.

What happens when n is 0 or 1?

These are base cases (Step 4 and 5) where the function returns immediately without recursion, ensuring the recursion ends.

Visual Quiz - 3 Questions

Look at the execution table, what is the value returned by fib(1) at Step 4?

A 0

B 1

C Undefined

D 2

💡 Hint

Check the 'Returned Value' column at Step 4 in the execution_table.

At which step does fib(3) get stored in memo?

A Step 6

B Step 9

C Step 8

D Step 10

💡 Hint

Look at the 'Operation' and 'memo State' columns to find when fib(3) is memoized.

If memo was not used, how would the number of calls change?

A Calls would increase due to repeated calculations

B Calls would stay the same

C Calls would decrease

D Calls would be zero

💡 Hint

Consider how overlapping subproblems cause repeated calls without memoization.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Reuse solutions of subproblems (memoization)
- Solve each subproblem once
- Combine subproblem solutions for final answer
- Key for efficient recursive algorithms like Fibonacci

Full Transcript

This concept shows how to solve problems efficiently by breaking them into smaller parts that overlap. When a subproblem is solved once, its answer is saved in a memo. Later, if the same subproblem is needed, the saved answer is reused instead of recalculating. This saves time and avoids repeated work. The example code calculates Fibonacci numbers using this idea. It checks if the answer is already in memo before computing. Base cases stop recursion. The memo grows as answers are stored. This method uses the properties of overlapping subproblems and optimal substructure to solve problems faster.