Overlapping Subproblems and Optimal Substructure in DSA C# - Build from Scratch

Understanding Overlapping Subproblems and Optimal Substructure with Fibonacci

📖 Scenario: Imagine you want to calculate the number of ways to climb stairs where you can take 1 or 2 steps at a time. This is similar to the Fibonacci sequence. Calculating this directly can be slow because you repeat the same calculations many times. We will learn how to use overlapping subproblems and optimal substructure concepts to solve this efficiently.

🎯 Goal: Build a simple program that calculates Fibonacci numbers using a method that remembers previous answers to avoid repeated work. This shows how overlapping subproblems and optimal substructure help in dynamic programming.

📋 What You'll Learn

Create an array to store Fibonacci numbers for reuse

Set up a base case for Fibonacci calculation

Write a loop to fill the array using previous results

Print the Fibonacci number for a given position

💡 Why This Matters

🌍 Real World

Calculating Fibonacci numbers efficiently is a classic example of dynamic programming, which is used in many real-world problems like resource allocation, route planning, and financial modeling.

💼 Career

Understanding overlapping subproblems and optimal substructure is essential for software engineers working on optimization problems, algorithm design, and performance improvements.

1

Create an array to store Fibonacci numbers

Create an integer array called fib with size 10 to store Fibonacci numbers.

DSA C#

# Your code here
// Create an integer array called fib with size 10

Hint

Use int[] fib = new int[10]; to create the array.

2

Set base cases for Fibonacci sequence

Set fib[0] to 0 and fib[1] to 1 as the base cases for the Fibonacci sequence.

DSA C#

int[] fib = new int[10];
// Set fib[0] = 0 and fib[1] = 1 as base cases

Hint

Remember the first two Fibonacci numbers are 0 and 1.

3

Fill the array using previous Fibonacci numbers

Use a for loop with variable i from 2 to 9 to fill fib[i] as the sum of fib[i - 1] and fib[i - 2].

DSA C#

int[] fib = new int[10];
fib[0] = 0;
fib[1] = 1;
// Use a for loop from i = 2 to 9 to fill fib[i] = fib[i - 1] + fib[i - 2]

Hint

Use a loop to build the Fibonacci sequence step by step.

4

Print the 9th Fibonacci number

Print the value of fib[9] using Console.WriteLine.

DSA C#

int[] fib = new int[10];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < 10; i++)
{
    fib[i] = fib[i - 1] + fib[i - 2];
}
// Print fib[9] below

Hint

The 9th Fibonacci number is 34. Use Console.WriteLine(fib[9]); to print it.

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