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.

Practice

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

easy

A. The problem requires sorting elements before solving.

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

C. The problem can be broken down into smaller subproblems that 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 solving.

2. Step 2: Match definition with options

   The problem can be broken down into smaller subproblems that are solved multiple times. correctly states that subproblems repeat and can be reused.

3. Final Answer:

   The problem can be broken down into smaller subproblems that 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 TypeScript syntax correctly declares a memoization object for storing subproblem results?

easy

A. let memo = new Map();

B. const memo: number[] = [];

C. var memo = {};

D. const memo: string = '';

Solution

1. Step 1: Identify suitable data structure for memoization

   Memoization stores key-value pairs of subproblems and results, so Map is ideal.

2. Step 2: Check options for correct TypeScript syntax

   let memo = new Map(); uses Map which is correct for memoization.

3. Final Answer:

   let memo = new Map<number, number>(); -> Option A

4. Quick Check:

   Memoization uses Map for key-value storage [OK]

Hint: Use Map for flexible key-value memo storage in TypeScript [OK]

Common Mistakes:

• Using empty object without type safety
• Declaring memo as a string instead of a collection
• Using array when keys are not sequential indices

3. Consider this TypeScript function using memoization for Fibonacci numbers:

function fib(n: number, memo = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}
console.log(fib(5));

What is the output printed?

medium

A. 8

B. 5

C. 3

D. Error

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) = fib(4) + fib(3), recursively calculated and stored to avoid repeats.

2. Step 2: Calculate fib(5) step-by-step

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

3. Final Answer:

   5 -> Option B

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting base cases n <= 1
• Assuming memo is reset each call

4. The following TypeScript code attempts to compute Fibonacci numbers with memoization but has a bug:

function fib(n: number, memo = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}
console.log(fib(5));

What is the main issue causing incorrect behavior?

medium

A. Memo object is not passed in recursive calls, so memoization fails.

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

C. Map is not initialized properly.

D. Return statement is missing.

Solution

1. Step 1: Analyze recursive calls and memo usage

   Recursive calls fib(n - 1) and fib(n - 2) do not pass the memo Map, so each call creates a new Map.

2. Step 2: Understand impact on memoization

   Without passing memo, results are not stored or reused, causing repeated calculations and no optimization.

3. Final Answer:

   Memo object is not passed in recursive calls, so memoization fails. -> Option A

4. Quick Check:

   Pass memo in recursive calls to reuse stored results [OK]

Hint: Always pass memo object in recursive calls for memoization [OK]

Common Mistakes:

• Not passing memo in recursive calls
• Changing base case unnecessarily
• Assuming Map auto-shares across calls

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:

const cost = [
  [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 a greedy approach picking the smallest adjacent cost at each step.

B. Use recursion without memoization to explore all paths.

C. Sort the grid and pick the smallest values.

D. Use dynamic programming to store minimum cost for each cell based on previous cells.

Solution

1. Step 1: Identify problem properties

   Minimum cost path has optimal substructure: cost to reach a cell depends on minimum cost to reach adjacent cells.

2. Step 2: Choose approach using overlapping subproblems

   Dynamic programming stores results for each cell to avoid recomputing paths (overlapping subproblems).

3. Final Answer:

   Use dynamic programming to store minimum cost for each cell based on previous cells. -> Option D

4. Quick Check:

   DP uses overlapping subproblems + optimal substructure [OK]

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

Common Mistakes:

• Using recursion without memoization causing slow performance
• Assuming greedy always finds minimum cost
• Sorting grid values unrelated to path costs