Overlapping Subproblems and Optimal Substructure in DSA Javascript - Build from Scratch

Understanding Overlapping Subproblems and Optimal Substructure with Fibonacci

📖 Scenario: Imagine you want to find the number of ways to climb stairs where you can take either 1 or 2 steps at a time. This is a classic problem that can be solved efficiently using the idea of overlapping subproblems and optimal substructure.

🎯 Goal: You will build a simple program to calculate the Fibonacci number for a given position using memoization. This will help you understand how overlapping subproblems and optimal substructure work together to optimize calculations.

📋 What You'll Learn

Create a function to calculate Fibonacci numbers

Use a cache object to store results of subproblems

Implement the recursive logic with memoization

Print the Fibonacci number for position 7

💡 Why This Matters

🌍 Real World

Many problems in computer science, like pathfinding, resource allocation, and sequence analysis, use overlapping subproblems and optimal substructure to optimize solutions.

💼 Career

Understanding these concepts is key for software engineers and data scientists to write efficient algorithms and solve complex problems quickly.

1

Create a cache object for memoization

Create an empty object called cache to store previously calculated Fibonacci numbers.

DSA Javascript

// Your code here

Hint

Think of cache as a notebook where you write down answers you already know so you don't have to calculate them again.

2

Define the Fibonacci function with memoization

Write a function called fib that takes a number n and returns the Fibonacci number at position n. Use the cache object to return cached results if available.

DSA Javascript

const cache = {};

// Define the fib function below
// Your code here

Hint

Use recursion and check if the answer for n is already in cache. If yes, return it. Otherwise, calculate and store it.

3

Calculate Fibonacci number for position 7

Call the fib function with the argument 7 and store the result in a variable called result.

DSA Javascript

const cache = {};

function fib(n) {
    if (n <= 1) {
        return n;
    }
    if (cache[n]) {
        return cache[n];
    }
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
}

// Calculate Fibonacci number for 7
// Your code here

Hint

Simply call fib(7) and save it in result.

4

Print the Fibonacci number for position 7

Print the value of the variable result using console.log.

DSA Javascript

const cache = {};

function fib(n) {
    if (n <= 1) {
        return n;
    }
    if (cache[n]) {
        return cache[n];
    }
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
}

const result = fib(7);

// Print the result
// Your code here

Hint

Use console.log(result) to display the answer.

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