Overlapping Subproblems and Optimal Substructure in DSA C++ - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Problem to solve

↓

Break into subproblems

↓

Check if subproblem solved before?

Yes No↓

Use stored

↓

Combine results

↓

Final solution

The problem is broken into smaller parts. If a part was solved before, reuse it. Otherwise, solve it and store the result. Combine all parts for the final answer.

Execution Sample

DSA C++

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

Calculates Fibonacci number using recursion, showing overlapping subproblems.

Execution Table

Step	Operation	Subproblem	Result Computed	Memo Used	Visual State
1	Call fib(4)	fib(4)	Not computed	No	fib(4) pending
2	Call fib(3)	fib(3)	Not computed	No	fib(4) waiting for fib(3) and fib(2)
3	Call fib(2)	fib(2)	Not computed	No	fib(3) waiting for fib(2) and fib(1)
4	Call fib(1)	fib(1)	1	No	fib(2) waiting for fib(1) and fib(0)
5	Return fib(1)	fib(1)	1	No	fib(2) waiting for fib(0)
6	Call fib(0)	fib(0)	0	No	fib(2) can compute now
7	Return fib(0)	fib(0)	0	No	fib(2) computed as 1
8	Compute fib(2)	fib(2)	1	No	fib(3) waiting for fib(1)
9	Return fib(2)	fib(2)	1	No	fib(3) waiting for fib(1)
10	Call fib(1)	fib(1)	1	Yes	fib(3) can compute now
11	Return fib(1)	fib(1)	1	Yes	fib(3) computed as 2
12	Compute fib(3)	fib(3)	2	No	fib(4) waiting for fib(2)
13	Call fib(2)	fib(2)	1	Yes	fib(4) can compute now
14	Return fib(2)	fib(2)	1	Yes	fib(4) computed as 3
15	Compute fib(4)	fib(4)	3	No	Final result 3
16	Return fib(4)	fib(4)	3	No	Done

💡 fib(4) computed by combining fib(3) and fib(2), recursion ends

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 11	After Step 15	Final
fib(4)	Not computed	Pending	Pending	Pending	3	3
fib(3)	Not computed	Pending	Pending	2	2	2
fib(2)	Not computed	Pending	1	1	1	1
fib(1)	Not computed	1	1	1	1	1
fib(0)	Not computed	Not computed	0	0	0	0

Key Moments - 3 Insights

Why does fib(2) get computed multiple times in the naive recursion?

Because the function calls fib(2) separately from fib(3) and fib(4) without storing results, as seen in steps 3 and 13 in the execution_table.

How does memoization avoid repeated work?

Memoization stores results after first computation (like fib(1) at step 10), so later calls reuse stored results instead of recomputing, reducing repeated calls.

What does 'optimal substructure' mean here?

It means the solution to fib(n) can be built from solutions to fib(n-1) and fib(n-2), as shown by combining results at steps 12 and 15.

Visual Quiz - 3 Questions

Look at the execution_table, at which step is fib(3) first computed?

A Step 11

B Step 10

C Step 12

D Step 9

💡 Hint

Check the 'Compute fib(3)' operation in the execution_table rows.

According to variable_tracker, what is the value of fib(2) after step 7?

A Not computed

B 1

C 2

D 0

💡 Hint

Look at the fib(2) row under 'After Step 7' column in variable_tracker.

If memoization was added, which step would no longer recompute fib(2)?

A Step 13

B Step 3

C Step 6

D Step 10

💡 Hint

Refer to execution_table where fib(2) is called again after first computation.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Subproblems overlap: same subproblem solved multiple times
- Store results (memoization) to reuse
- Optimal substructure: final solution built from subproblem solutions
- Example: Fibonacci uses fib(n-1) + fib(n-2)
- Avoids exponential time by reusing results

Full Transcript

This concept shows how some problems can be split into smaller parts that repeat. When a part is solved once, we save its answer to avoid doing it again. This saves time and makes the solution faster. The example is the Fibonacci sequence, where fib(n) depends on fib(n-1) and fib(n-2). The execution table shows how the function calls overlap and how results can be reused. The variable tracker shows the values of each subproblem as the recursion unfolds. Key moments explain why repeated work happens and how storing results helps. The quiz tests understanding of when subproblems are computed and reused.

Practice

1. Which of the following best describes the property of Overlapping Subproblems in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems which 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 the solution process.

2. Step 2: Match the definition to options

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

3. Final Answer:

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

4. Quick Check:

   Overlapping Subproblems = Smaller repeated subproblems [OK]

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

Common Mistakes:

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

2. Which of the following C++ function signatures correctly represents a memoized Fibonacci function using dynamic programming?

easy

A. void fib(int n);

B. int fib();

C. int fib(int n);

D. int fib(int n, int memo[]);

Solution

1. Step 1: Identify memoization parameters

   Memoization requires an extra data structure (like an array) to store results of subproblems.

2. Step 2: Check function signatures

   int fib(int n, int memo[]); includes an array parameter to store memoized results, which is necessary for memoization.

3. Final Answer:

   int fib(int n, int memo[]); -> Option D

4. Quick Check:

   Memoization needs storage parameter [OK]

Hint: Memoized functions need extra storage parameter [OK]

Common Mistakes:

• Ignoring the memo array parameter
• Using void return type for Fibonacci
• Not passing any parameters for recursion

3. What is the output of the following C++ code snippet?

int fib(int n, int memo[]) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

int main() {
  int n = 5;
  int memo[6];
  for(int i = 0; i <= n; i++) memo[i] = -1;
  std::cout << fib(n, memo);
  return 0;
}

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Understand Fibonacci calculation

   fib(5) = fib(4) + fib(3). Using memoization, fib(5) = 8.

2. Step 2: Trace the code execution

   Memo array initialized with -1, so recursive calls compute and store values. fib(5) returns 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   fib(5) = 8 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting zero-based indexing
• Assuming memo array is not initialized

4. Identify the error in the following code snippet implementing memoized Fibonacci:

int fib(int n, int memo[]) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

medium

A. The function should return void instead of int.

B. Base cases should return -1 instead of 0 or 1.

C. Memo array should be initialized with -1, not 0.

D. The memo array size is not checked inside the function.

Solution

1. Step 1: Check memoization condition

   The code checks if memo[n] != 0 to decide if value is computed, but 0 is a valid Fibonacci value.

2. Step 2: Correct initialization for memo array

   Memo array should be initialized with a value like -1 to indicate uncomputed states, avoiding confusion with valid 0.

3. Final Answer:

   Memo array should be initialized with -1, not 0. -> Option C

4. Quick Check:

   Use -1 for uninitialized memo values [OK]

Hint: Initialize memo with -1 to distinguish computed from uncomputed [OK]

Common Mistakes:

• Using 0 as default memo value causing wrong cache hits
• Changing base case return values incorrectly
• Ignoring memo array size checks

5. Given the problem of finding the minimum cost path in a grid from top-left to bottom-right, which property justifies using dynamic programming to solve it efficiently?

hard

A. The problem has both overlapping subproblems and optimal substructure.

B. The problem has optimal substructure but no overlapping subproblems.

C. The problem has overlapping subproblems but no optimal substructure.

D. The problem has neither overlapping subproblems nor optimal substructure.

Solution

1. Step 1: Understand minimum cost path problem

   The problem breaks into smaller subproblems (paths to cells) that overlap and solutions combine optimally.

2. Step 2: Identify properties

   It has overlapping subproblems (same cells computed multiple times) and optimal substructure (optimal path uses optimal subpaths).

3. Final Answer:

   The problem has both overlapping subproblems and optimal substructure. -> Option A

4. Quick Check:

   Minimum cost path = Overlapping + Optimal substructure [OK]

Hint: Check if subproblems repeat and combine optimally [OK]

Common Mistakes:

• Thinking only one property applies
• Confusing optimal substructure with greedy choice
• Ignoring repeated subproblems in grid paths