Overlapping Subproblems and Optimal Substructure in DSA Javascript - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Start Problem

↓

Break into Subproblems

↓

Check if Subproblem Result Known?

Yes→Use Stored Result

No↓

Solve Subproblem Recursively

↓

Store Result for Reuse

↓

Combine Subproblem Results

↓

Final Solution

This flow shows how a problem is broken into smaller parts, solved once, stored, and reused to build the final answer efficiently.

Execution Sample

DSA Javascript

function fib(n, memo = {}) {
  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];
}
console.log(fib(5));

Calculates Fibonacci number 5 using memoization to avoid repeated calculations.

Execution Table

Step	Operation	Subproblem	Memo Before	Memo After	Returned Value
1	Call fib(5)	fib(5)	{}	{}	pending
2	Call fib(4)	fib(4)	{}	{}	pending
3	Call fib(3)	fib(3)	{}	{}	pending
4	Call fib(2)	fib(2)	{}	{}	pending
5	Call fib(1)	fib(1)	{}	{}	1
6	Call fib(0)	fib(0)	{}	{}	0
7	Compute fib(2)	fib(2)	{}	{2:1}	1
8	Compute fib(3)	fib(3)	{2:1}	{2:1,3:2}	2
9	Call fib(1)	fib(1)	{2:1}	{2:1}	1
10	Compute fib(4)	fib(4)	{2:1,3:2}	{2:1,3:2,4:3}	3
11	Call fib(2)	fib(2)	{2:1,3:2}	{2:1,3:2}	1
12	Compute fib(5)	fib(5)	{2:1,3:2,4:3}	{2:1,3:2,4:3,5:5}	5
13	Return final result	fib(5)	{2:1,3:2,4:3,5:5}	{2:1,3:2,4:3,5:5}	5

💡 All subproblems solved and stored; final fib(5) returned as 5.

Variable Tracker

Variable	Start	After Step 7	After Step 8	After Step 10	After Step 12	Final
memo	{}	{2:1}	{2:1,3:2}	{2:1,3:2,4:3}	{2:1,3:2,4:3,5:5}	{2:1,3:2,4:3,5:5}
Returned Value	pending	1	2	3	5	5

Key Moments - 3 Insights

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

Checking memo[n] (see steps 3,9,11) avoids recalculating fib(n) if already solved, saving time by reusing stored results.

How does the function avoid infinite recursion?

Base cases at steps 5 and 6 return values directly for fib(1) and fib(0), stopping recursion from going deeper.

Why is the memo object updated after recursive calls?

After computing fib(n-1) and fib(n-2), the result is stored in memo (steps 7, 8, 10, 12) so future calls can reuse it, showing optimal substructure.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value returned by fib(3) at step 8?

A 1

B 2

C 3

D 5

💡 Hint

Check the 'Returned Value' column at step 8 in the execution_table.

At which step does the memo first store a value for fib(4)?

A Step 10

B Step 8

C Step 7

D Step 12

💡 Hint

Look at the 'Memo After' column for when key 4 appears in the execution_table.

If we remove the memo check, how would the execution_table change?

A No change in calls or memo

B Fewer calls and faster returns

C More repeated calls and no memo updates

D Memo would store incorrect values

💡 Hint

Refer to the memo usage in the execution_table steps where repeated calls are avoided.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Solve each subproblem once and store result (memoization)
- Reuse stored results to avoid repeated work
- Combine subproblem results for final answer
- Key for efficient recursive algorithms like Fibonacci

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 solve it once and save the answer. Later, if we need it again, we just use the saved answer. This saves time and makes the program faster. The example code calculates Fibonacci numbers using this idea. It checks if the answer is already saved before calculating. If not, it calculates, saves, and returns it. This way, the program avoids repeating the same calculations over and over. The flow starts by breaking the problem, checking saved answers, solving new parts, saving them, and finally combining all to get the final result.

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 solved 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 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 to save time.

3. Final Answer:

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

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 all DP problems
• Assuming recursion alone solves overlapping subproblems

2. Which of the following JavaScript function definitions correctly implements memoization for a Fibonacci function?

easy

A. function fib(n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

B. const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; }

C. function fib(n) { let result = 0; for(let i=0; i

D. function fib(n) { return n * fib(n-1); }

Solution

1. Step 1: Identify memoization pattern

   Memoization stores results in a cache object to avoid repeated calculations.

2. Step 2: Check each option

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } uses an object 'memo' to store and reuse Fibonacci results correctly.

3. Final Answer:

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } -> Option B

4. Quick Check:

   Memoization uses cache object = const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } [OK]

Hint: Look for cache object usage to store computed results [OK]

Common Mistakes:

• Not using a cache to store results
• Incorrect base case handling
• Using loops instead of recursion for memoization

3. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 3

B. 8

C. 5

D. Undefined

Solution

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

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc.

2. Step 2: Calculate Fibonacci values

   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:

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

4. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(0));

medium

A. 0

B. 1

C. undefined

D. Infinite recursion

Solution

1. Step 1: Trace fib(0)

   fib(0): n = 0 <= 1, so return 0 immediately. Memo check and recursion not reached.

2. Step 2: Output

   console.log(0) prints 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   fib(0) = 0 [OK]

Hint: Base case n <= 1 executes before memo check [OK]

Common Mistakes:

• Thinking memo[n] check runs for base cases n <= 1
• Believing falsy memo[0] causes undefined return
• Forgetting base case includes n = 0

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. Which property allows using dynamic programming to solve this efficiently?

hard

A. Greedy choice: Always pick the cell with the smallest immediate cost.

B. Overlapping subproblems: Each cell's cost is unique and never reused.

C. Divide and conquer: Solve each half of the grid independently.

D. Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells.

Solution

1. Step 1: Understand minimum cost path problem

   The cost to reach a cell depends on the best path to its neighbors (top or left).

2. Step 2: Identify optimal substructure

   The problem can be solved by combining optimal solutions of smaller subproblems (cells).

3. Final Answer:

   Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells. -> Option D

4. Quick Check:

   Optimal substructure enables DP for grid path [OK]

Hint: Look for problems where solutions build from smaller optimal solutions [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Assuming greedy always works for grid path
• Ignoring dependency between subproblems