Overlapping Subproblems and Optimal Substructure in DSA Typescript

Mental Model

Some problems can be broken into smaller parts that repeat, and the best solution uses the best answers to those 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 (reused)  Subproblem B (reused)

Dry Run Walkthrough

Input: Calculate Fibonacci number for 5 using overlapping subproblems and optimal substructure

Goal: Show how smaller Fibonacci numbers are reused to find the answer efficiently

Step 1: Calculate fib(5) by breaking into fib(4) + fib(3)

fib(5) = fib(4) + fib(3)

Why: We break the problem into smaller parts to solve step by step

Step 2: Calculate fib(4) by fib(3) + fib(2)

fib(5) = [fib(3) + fib(2)] + fib(3)

Why: fib(4) also breaks down, but fib(3) appears again

Step 3: Calculate fib(3) by fib(2) + fib(1)

fib(5) = [[fib(2) + fib(1)] + fib(2)] + fib(3)

Why: fib(3) breaks down further, fib(2) repeats multiple times

Step 4: Reuse fib(2) and fib(1) values instead of recalculating

fib(5) = [[1 + 1] + 1] + [1 + 1]

Why: Reusing results saves time and avoids repeated work

Step 5: Sum all values to get fib(5) = 5

fib(5) = 5

Why: Combining all solved parts gives the final answer

Result:

fib(5) = 5

Annotated Code

DSA Typescript

class Fibonacci {
  private memo: Map<number, number> = new Map();

  fib(n: number): number {
    if (n <= 1) return n; // base case
    if (this.memo.has(n)) return this.memo.get(n)!; // reuse stored result

    const result = this.fib(n - 1) + this.fib(n - 2); // break into subproblems
    this.memo.set(n, result); // store result for reuse
    return result;
  }
}

const fibCalc = new Fibonacci();
console.log(`fib(5) = ${fibCalc.fib(5)}`);

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

stop recursion when problem is smallest

if (this.memo.has(n)) return this.memo.get(n)!; // reuse stored result

check if subproblem already solved to avoid repeat work

const result = this.fib(n - 1) + this.fib(n - 2); // break into subproblems

divide problem into smaller overlapping parts

this.memo.set(n, result); // store result for reuse

save answer to reuse later, showing optimal substructure

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each Fibonacci number from 0 to n is calculated once and reused

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

vs Alternative: Compared to naive recursion with O(2^n) time, this approach is much faster by reusing answers

Edge Cases

n = 0 or n = 1 (smallest inputs)

Returns n immediately as base case without recursion

DSA Typescript

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

Repeated calls with same n

Uses memoized result to avoid recalculation

DSA Typescript

if (this.memo.has(n)) return this.memo.get(n)!; // reuse stored result

When to Use This Pattern

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

Common Mistakes

Mistake: Not storing results of subproblems causing repeated calculations
Fix: Use a memo structure to save and reuse answers for subproblems

Mistake: Missing base case causing infinite recursion
Fix: Add base case to stop recursion when problem is smallest

Summary

It breaks problems into smaller overlapping parts and reuses their best answers.

Use it when a problem can be divided into repeated smaller problems with optimal solutions.

The key is to save answers to subproblems so you don't solve the same thing twice.