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

This flow shows how a problem is broken into smaller parts, solved recursively, and solutions are saved to avoid repeating work.

Execution Sample

DSA C#

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];
}

This code calculates Fibonacci numbers using memoization to reuse results of overlapping subproblems.

Execution Table

Step	Operation	n	memo[n]	Recursive Calls	Visual State (memo array)
1	Call Fib(4)	4	-1	Fib(3), Fib(2)	[-1, -1, -1, -1, -1]
2	Call Fib(3)	3	-1	Fib(2), Fib(1)	[-1, -1, -1, -1, -1]
3	Call Fib(2)	2	-1	Fib(1), Fib(0)	[-1, -1, -1, -1, -1]
4	Call Fib(1)	1	1 (base case)	None	[-1, -1, -1, -1, -1]
5	Return Fib(1) = 1	1	1	None	[-1, -1, -1, -1, -1]
6	Call Fib(0)	0	0 (base case)	None	[-1, -1, -1, -1, -1]
7	Return Fib(0) = 0	0	0	None	[-1, -1, -1, -1, -1]
8	Calculate Fib(2) = 1 + 0 = 1	2	1	None	[-1, -1, 1, -1, -1]
9	Return Fib(2) = 1	2	1	None	[-1, -1, 1, -1, -1]
10	Call Fib(1)	1	1 (base case)	None	[-1, -1, 1, -1, -1]
11	Return Fib(1) = 1	1	1	None	[-1, -1, 1, -1, -1]
12	Calculate Fib(3) = 1 + 1 = 2	3	2	None	[-1, -1, 1, 2, -1]
13	Return Fib(3) = 2	3	2	None	[-1, -1, 1, 2, -1]
14	Call Fib(2)	2	1 (memoized)	None	[-1, -1, 1, 2, -1]
15	Return Fib(2) = 1	2	1	None	[-1, -1, 1, 2, -1]
16	Calculate Fib(4) = 2 + 1 = 3	4	3	None	[-1, -1, 1, 2, 3]
17	Return Fib(4) = 3	4	3	None	[-1, -1, 1, 2, 3]

💡 Fib(4) computed using stored results, recursion ends.

Variable Tracker

Variable	Start	After Step 8	After Step 12	After Step 16	Final
n	4	2	3	4	4
memo[2]	-1	1	1	1	1
memo[3]	-1	-1	2	2	2
memo[4]	-1	-1	-1	3	3

Key Moments - 3 Insights

Why do we check if memo[n] != -1 before recursive calls?

Because if memo[n] is not -1, it means we already solved this subproblem (see step 14), so we return the stored result to avoid repeating work.

Why do we have two recursive calls for Fib(n)?

Because Fib(n) depends on Fib(n-1) and Fib(n-2) (step 1), showing the problem breaks into smaller overlapping subproblems.

How does storing results help in this example?

Storing results in memo array (steps 8, 12, 16) prevents recalculating the same Fib values multiple times, saving time.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo[3] after step 12?

A 2

B -1

C 1

D 3

💡 Hint

Check the 'Visual State' column at step 12 in the execution_table.

At which step does the condition memo[n] != -1 first become true?

A Step 8

B Step 10

C Step 14

D Step 4

💡 Hint

Look for the first step where Fib(n) returns a memoized value without recursion.

If we did not store results in memo, how would the execution table change?

A Fewer recursive calls

B More recursive calls and repeated calculations

C No change in recursive calls

D Memo array would have more values

💡 Hint

Think about how memoization avoids repeated work shown in the table.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Solve subproblems recursively
- Store results to reuse (memoization)
- Avoid repeated work on same subproblems
- Combine subproblem solutions for final answer

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 save the answer once and reuse it. The example uses Fibonacci numbers, where each number depends on the two before it. We check if we already know the answer before calculating. This saves time and makes the program faster.

Practice

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

easy

A. The problem has a unique solution that can be found without recursion.

B. The problem can be broken down into smaller subproblems which are solved multiple times.

C. The problem requires sorting before solving.

D. The problem can only be solved using greedy algorithms.

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 with 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 B

4. Quick Check:

   Overlapping Subproblems = The problem can be broken down into smaller subproblems which are solved multiple times. [OK]

Hint: Look for repeated smaller problems solved multiple times [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking greedy algorithms always apply
• Ignoring recursion or repeated calculations

2. Which of the following C# method signatures correctly represents a memoized Fibonacci function using recursion?

easy

A. string Fib(int n, Dictionary memo)

B. void Fib(int n)

C. int Fib(int n, int[] memo)

D. int Fib(int n, Dictionary memo)

Solution

1. Step 1: Identify correct return type and parameters

   The Fibonacci function returns an integer and uses a dictionary to store computed values for memoization.

2. Step 2: Check options for matching signature

   int Fib(int n, Dictionary memo) returns int and takes an int and a Dictionary for memo, which is correct for memoized recursion.

3. Final Answer:

   int Fib(int n, Dictionary memo) -> Option D

4. Quick Check:

   Memoized Fib signature = int Fib(int n, Dictionary memo) [OK]

Hint: Memoized functions usually take a cache parameter like Dictionary [OK]

Common Mistakes:

• Using void return type instead of int
• Using wrong data structure for memo
• Returning string instead of int

3. What is the output of the following C# code?

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

static void Main() {
  int n = 5;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Understand Fibonacci calculation for n=5

   Fibonacci sequence: 0,1,1,2,3,5,... So Fib(5) = 5.

2. Step 2: Trace memoized calls

   Memo array caches results to avoid repeated calls, final result printed is Fib(5) = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence values for small n [OK]

Common Mistakes:

• Confusing Fib(5) with Fib(6)
• Ignoring memoization effect
• Assuming zero-based indexing for output

4. Identify the error in the following C# code implementing a memoized Fibonacci function:

static 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];
}

static void Main() {
  int n = 4;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. The memo array is not initialized with -1, so memo[n] != -1 check fails.

B. The base case should return 0 instead of n.

C. The function should return void instead of int.

D. The memo array size is too large.

Solution

1. Step 1: Check memo array initialization

   The memo array is created but not initialized to -1, so all values default to 0.

2. Step 2: Analyze memo[n] != -1 condition

   Since memo[n] starts at 0, the condition memo[n] != -1 is always true for n>0, causing incorrect memo hits.

3. Final Answer:

   The memo array is not initialized with -1, so memo[n] != -1 check fails. -> Option A

4. Quick Check:

   Uninitialized memo array causes wrong memo check [OK]

Hint: Initialize memo with sentinel values matching your check [OK]

Common Mistakes:

• Not initializing memo array properly
• Incorrect base case return values
• Wrong return type for recursive function

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:

int[,] cost = {
  {1, 3, 5, 8},
  {4, 2, 1, 7},
  {4, 3, 2, 3}
};

Which approach best uses Overlapping Subproblems and Optimal Substructure to solve this efficiently?

hard

A. Calculate all paths and pick the minimum cost path at the end.

B. Use a greedy approach picking the minimum cost neighbor at each step.

C. Use recursion with memoization to store minimum cost for each cell.

D. Use a stack to store all possible paths and backtrack.

Solution

1. Step 1: Understand problem structure

   The minimum cost path problem has overlapping subproblems because many paths share subpaths, and optimal substructure because the best path to a cell depends on best paths to neighbors.

2. Step 2: Choose efficient approach

   Recursion with memoization stores results of subproblems to avoid recomputation, efficiently solving the problem.

3. Final Answer:

   Use recursion with memoization to store minimum cost for each cell. -> Option C

4. Quick Check:

   Memoized recursion fits overlapping subproblems and optimal substructure [OK]

Hint: Memoize subproblem results to avoid repeated calculations [OK]

Common Mistakes:

• Using greedy approach which may fail for this problem
• Trying all paths causing exponential time
• Using stack/backtracking without memoization