Overlapping Subproblems and Optimal Substructure in DSA C++

Mental Model

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

Analogy: Imagine building a big Lego castle by reusing the same small Lego pieces many times instead of making new ones each time.

Problem
  ↓
Subproblem A -> Subproblem B -> Subproblem C
  ↓           ↓
Subproblem A (repeated)

Optimal solution = best answers combined

Dry Run Walkthrough

Input: Calculate Fibonacci number for 5 using recursion

Goal: Show how the same smaller problems are solved multiple times and how best answers build up

Step 1: Calculate fib(5) by calling 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 calling fib(3) and fib(2)

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

Why: fib(4) depends on fib(3) and fib(2), but fib(3) is also needed separately

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

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

Why: fib(3) is needed twice, showing overlapping subproblems

Step 4: Calculate fib(2) by calling fib(1) and fib(0)

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

Why: fib(2) is a base for fib(3) and fib(4), repeated calls show overlap

Step 5: Combine results from fib(1) and fib(0) to get fib(2), then build up to fib(5)

fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5

Why: Optimal substructure means fib(5) is sum of best answers fib(4) and fib(3)

Result:

fib(5) = 5
Overlapping subproblems: fib(3) and fib(2) calculated multiple times
Optimal substructure: fib(n) = fib(n-1) + fib(n-2)

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>

class Fibonacci {
public:
    std::unordered_map<int, int> memo;

    int fib(int n) {
        if (n <= 1) return n; // base case
        if (memo.find(n) != memo.end()) return memo[n]; // reuse solved subproblem
        // solve subproblems and combine
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
};

int main() {
    Fibonacci fibCalc;
    int n = 5;
    std::cout << "fib(" << n << ") = " << fibCalc.fib(n) << std::endl;
    return 0;
}

if (n <= 1) return n; // base case

stop recursion at smallest problems

if (memo.find(n) != memo.end()) return memo[n]; // reuse solved subproblem

check if subproblem already solved to avoid repeat work

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

combine best answers of smaller subproblems to solve current

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each subproblem fib(k) is solved once and stored

Space: O(n) for the memoization map storing results of subproblems

vs Alternative: Without memoization, time is O(2^n) due to repeated calculations of same subproblems

Edge Cases

n = 0 or n = 1 (smallest inputs)

Returns n immediately as base case

DSA C++

if (n <= 1) return n; // base case

Repeated calls for same n

Memoization returns stored result, avoiding recomputation

DSA C++

if (memo.find(n) != memo.end()) return memo[n]; // reuse solved subproblem

When to Use This Pattern

When a problem can be split into smaller repeated parts and the best solution uses best answers to these parts, look for overlapping subproblems and optimal substructure to apply dynamic programming.

Common Mistakes

Mistake: Not storing results of subproblems causing repeated work and slow code
Fix: Use memoization to save and reuse answers of solved subproblems

Mistake: Not identifying that the problem can be broken into smaller optimal parts
Fix: Check if the problem's solution can be built from solutions to smaller subproblems

Summary

It finds solutions by reusing answers to repeated smaller problems and combining them optimally.

Use it when a problem can be divided into overlapping smaller problems with best partial solutions.

The key is that solving once and reusing answers saves time and builds the best overall solution.

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