Overlapping Subproblems and Optimal Substructure in DSA Javascript

Mental Model

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

Analogy: Imagine building a big wall with Lego blocks. If you already built a small section, you don't rebuild it again; you reuse it. Also, the best wall is made by putting together the best small sections.

Problem
  ↓
Smaller Problem 1 -> Smaller Problem 2 -> Smaller Problem 3
  ↓               ↓                 ↓
Reuse answers ← Reuse answers ← Reuse answers

Dry Run Walkthrough

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

Goal: Show how smaller Fibonacci numbers are reused and combined to get the final answer

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

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

Why: fib(5) depends on fib(4) and fib(3) because of the problem's structure

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) breaks down further, but 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) also breaks down, fib(2) repeats multiple times

Step 4: Reuse fib(3) and fib(2) results instead of recalculating

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

Why: Overlapping subproblems mean we save time by reusing answers

Step 5: Combine cached results to get fib(5) = fib(4) + fib(3) = 3 + 2 = 5

fib(5) = 5

Why: Optimal substructure means the best answer uses best smaller answers

Result:

fib(5) = 5

Annotated Code

DSA Javascript

class Fibonacci {
  constructor() {
    this.memo = {};
  }

  fib(n) {
    if (n <= 1) return n; // base case
    if (this.memo[n] !== undefined) return this.memo[n]; // reuse cached result

    // calculate fib(n-1) and fib(n-2) recursively
    const result = this.fib(n - 1) + this.fib(n - 2);
    this.memo[n] = result; // store result for reuse
    return result;
  }
}

const fibCalc = new Fibonacci();
console.log(fibCalc.fib(5));

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

stop recursion when n is 0 or 1

if (this.memo[n] !== undefined) return this.memo[n]; // reuse cached result

return stored answer to avoid repeated work

const result = this.fib(n - 1) + this.fib(n - 2);

combine smaller subproblems to build solution

this.memo[n] = result; // store result for reuse

save answer for future calls

Output

5

Complexity Analysis

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

Space: O(n) for storing the memoization cache of size n

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

Edge Cases

n = 0 or n = 1

Returns n immediately as base case

DSA Javascript

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

Repeated calls with same n

Returns cached result without recalculation

DSA Javascript

if (this.memo[n] !== undefined) return this.memo[n]; // reuse cached result

When to Use This Pattern

When a problem can be broken into smaller overlapping parts and the best solution uses best smaller solutions, use dynamic programming with memoization.

Common Mistakes

Mistake: Not caching results causes repeated calculations and slow performance
Fix: Add memoization to store and reuse results of subproblems

Mistake: Missing base case leads to infinite recursion
Fix: Include base case to stop recursion at smallest inputs

Summary

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

Use it when subproblems repeat and the overall solution depends on combining them.

The key is to save answers to small parts and build up the big answer efficiently.

Practice

1. Which of the following best describes the overlapping subproblems property in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems that 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 solving.

2. Step 2: Match with options

   The problem can be broken down into smaller subproblems that are solved multiple times. correctly states that subproblems repeat and can be reused to save time.

3. Final Answer:

   The problem can be broken down into smaller subproblems that are solved multiple times. -> Option A

4. Quick Check:

   Overlapping subproblems = repeated smaller problems [OK]

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

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking sorting is required for all DP problems
• Assuming recursion alone solves overlapping subproblems

2. Which of the following JavaScript function definitions correctly implements memoization for a Fibonacci function?

easy

A. function fib(n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

B. const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; }

C. function fib(n) { let result = 0; for(let i=0; i

D. function fib(n) { return n * fib(n-1); }

Solution

1. Step 1: Identify memoization pattern

   Memoization stores results in a cache object to avoid repeated calculations.

2. Step 2: Check each option

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } uses an object 'memo' to store and reuse Fibonacci results correctly.

3. Final Answer:

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } -> Option B

4. Quick Check:

   Memoization uses cache object = const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } [OK]

Hint: Look for cache object usage to store computed results [OK]

Common Mistakes:

• Not using a cache to store results
• Incorrect base case handling
• Using loops instead of recursion for memoization

3. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 3

B. 8

C. 5

D. Undefined

Solution

1. Step 1: Trace fib(5) calls with memo

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc.

2. Step 2: Calculate Fibonacci values

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

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5,8... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Miscounting base cases

4. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(0));

medium

A. 0

B. 1

C. undefined

D. Infinite recursion

Solution

1. Step 1: Trace fib(0)

   fib(0): n = 0 <= 1, so return 0 immediately. Memo check and recursion not reached.

2. Step 2: Output

   console.log(0) prints 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   fib(0) = 0 [OK]

Hint: Base case n <= 1 executes before memo check [OK]

Common Mistakes:

• Thinking memo[n] check runs for base cases n <= 1
• Believing falsy memo[0] causes undefined return
• Forgetting base case includes n = 0

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. Which property allows using dynamic programming to solve this efficiently?

hard

A. Greedy choice: Always pick the cell with the smallest immediate cost.

B. Overlapping subproblems: Each cell's cost is unique and never reused.

C. Divide and conquer: Solve each half of the grid independently.

D. Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells.

Solution

1. Step 1: Understand minimum cost path problem

   The cost to reach a cell depends on the best path to its neighbors (top or left).

2. Step 2: Identify optimal substructure

   The problem can be solved by combining optimal solutions of smaller subproblems (cells).

3. Final Answer:

   Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells. -> Option D

4. Quick Check:

   Optimal substructure enables DP for grid path [OK]

Hint: Look for problems where solutions build from smaller optimal solutions [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Assuming greedy always works for grid path
• Ignoring dependency between subproblems