Overlapping Subproblems and Optimal Substructure in DSA C#

Mental Model

Some big problems can be broken into smaller problems that repeat, and the best solution uses the best answers to these smaller parts.

Analogy: Imagine building a big Lego castle by reusing the same small Lego towers you built before instead of making new ones every time.

Big Problem
  ↓
Small Problem 1 -> Small Problem 2 -> Small Problem 1 (repeats)
  ↓                 ↓
Best answer uses saved answers to small problems

Dry Run Walkthrough

Input: Calculate Fibonacci number for 5 using recursion

Goal: Show how the same smaller problems repeat and how saving answers helps

Step 1: Calculate fib(5) by calculating fib(4) and fib(3)

fib(5) -> fib(4), fib(3)

Why: To find fib(5), we need fib(4) and fib(3)

Step 2: Calculate fib(4) by calculating fib(3) and fib(2)

fib(5) -> fib(4) -> fib(3), fib(2); fib(3)

Why: fib(4) depends on fib(3) and fib(2), fib(3) is repeated

Step 3: Calculate fib(3) by calculating fib(2) and fib(1)

fib(5) -> fib(4) -> fib(3) -> fib(2), fib(1); fib(2); fib(3)

Why: fib(3) repeats, fib(2) repeats, showing overlapping subproblems

Step 4: Save answers of fib(2) and fib(3) to reuse

Saved fib(2) = 1, fib(3) = 2

Why: Saving answers avoids recalculating the same problems

Step 5: Use saved answers to calculate fib(4) and fib(5)

fib(4) = fib(3) + fib(2) = 2 + 1 = 3; fib(5) = fib(4) + fib(3) = 3 + 2 = 5

Why: Using saved answers speeds up calculation

Result:

fib(5) = 5

Annotated Code

DSA C#

using System;

class Fibonacci {
    private int[] memo;

    public Fibonacci(int n) {
        memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1; // -1 means not calculated yet
        }
    }

    public int Fib(int n) {
        if (n <= 1) return n; // base case
        if (memo[n] != -1) return memo[n]; // return saved answer

        // calculate and save answer
        memo[n] = Fib(n - 1) + Fib(n - 2);
        return memo[n];
    }

    static void Main() {
        int n = 5;
        Fibonacci fibCalc = new Fibonacci(n);
        int result = fibCalc.Fib(n);
        Console.WriteLine($"fib({n}) = {result}");
    }
}

if (memo[n] != -1) return memo[n];

return saved answer to avoid recalculating overlapping subproblems

memo[n] = Fib(n - 1) + Fib(n - 2);

calculate answer using smaller subproblems and save it

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each subproblem fib(i) is calculated once and saved

Space: O(n) for the memo array storing answers to subproblems

vs Alternative: Naive recursion is O(2^n) because it recalculates the same subproblems many times; memoization reduces this to O(n)

Edge Cases

n = 0 or n = 1

Returns n immediately as base case without recursion

DSA C#

if (n <= 1) return n;

Large n

Memoization prevents exponential time by saving results

DSA C#

if (memo[n] != -1) return memo[n];

When to Use This Pattern

When a problem asks for an answer built from smaller repeated parts, look for overlapping subproblems and optimal substructure to use memoization or dynamic programming.

Common Mistakes

Mistake: Not saving the results of subproblems, causing repeated calculations
Fix: Use a memo array or dictionary to save and reuse answers

Mistake: Missing base cases causing infinite recursion
Fix: Always include base cases like n <= 1 to stop recursion

Summary

It breaks big problems into smaller repeated parts and saves answers to avoid repeating work.

Use it when a problem can be divided into smaller overlapping subproblems with optimal substructure.

The key is to save answers to small problems so you never solve the same problem twice.

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