Overlapping Subproblems and Optimal Substructure in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does Overlapping Subproblems mean in dynamic programming?

It means the problem can be broken down into smaller parts that repeat. Instead of solving the same small problem many times, we solve it once and reuse the answer.

beginner

Explain Optimal Substructure in simple words.

A problem has optimal substructure if the best solution can be made by combining the best solutions of its smaller parts.

beginner

Why is overlapping subproblems important for dynamic programming?

Because it allows us to save time by storing answers to small problems and reusing them, instead of solving the same problem again and again.

intermediate

Give an example of a problem that shows both overlapping subproblems and optimal substructure.

The Fibonacci sequence is a classic example. Calculating Fibonacci(n) uses Fibonacci(n-1) and Fibonacci(n-2), which overlap, and the best answer depends on the best answers to smaller Fibonacci numbers.

intermediate

How does memoization relate to overlapping subproblems?

Memoization is a technique to remember answers to subproblems so we don't solve them again. It works because of overlapping subproblems.

Which of these best describes overlapping subproblems?

A The problem cannot be solved by combining smaller solutions.

B The problem has no smaller parts.

C The problem solution depends only on the first step.

D The problem can be divided into smaller problems that repeat.

Overlapping subproblems means smaller parts repeat and can be reused.

What does optimal substructure mean?

A The solution is random.

B The problem has no solution.

C The best solution is made from best solutions of smaller parts.

D The problem cannot be divided.

Optimal substructure means combining best smaller solutions gives the best big solution.

Which technique uses overlapping subproblems to save time?

A Sorting

B Memoization

C Brute force

D Greedy algorithm

Memoization stores answers to repeated subproblems to avoid repeated work.

Which problem is a classic example of overlapping subproblems and optimal substructure?

A Fibonacci sequence

B Sorting numbers

C Finding max in array

D Printing text

Fibonacci uses answers to smaller Fibonacci numbers repeatedly and combines them optimally.

Why is dynamic programming efficient?

A It reuses answers to repeated subproblems.

B It guesses answers randomly.

C It solves problems only once without reuse.

D It ignores smaller problems.

Dynamic programming saves time by reusing answers to overlapping subproblems.

Explain in your own words what overlapping subproblems and optimal substructure mean and why they matter in solving problems efficiently.

Think about breaking problems into smaller parts and reusing answers.

Describe how the Fibonacci sequence problem demonstrates overlapping subproblems and optimal substructure.

Focus on how Fibonacci(n) depends on Fibonacci(n-1) and Fibonacci(n-2).

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