Overlapping Subproblems and Optimal Substructure in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following TypeScript code that calculates Fibonacci numbers using memoization?

DSA Typescript

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

A 13

B 5

C 8

D 3

💡 Hint

Remember that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

The function uses memoization to efficiently calculate Fibonacci numbers. fib(5) returns 5 because the sequence is 0,1,1,2,3,5...

🧠 Conceptual

intermediate

Identifying Overlapping Subproblems

Which of the following problems best demonstrates the concept of overlapping subproblems?

A Computing Fibonacci numbers using recursion without memoization

B Finding the shortest path in a graph using Dijkstra's algorithm

C Sorting an array using quicksort

D Calculating factorial of a number using recursion

💡 Hint

Overlapping subproblems means the same smaller problems are solved multiple times.

Computing Fibonacci numbers recursively without memoization recalculates the same values many times, showing overlapping subproblems.

🔧 Debug

advanced

Fix the Memoization Bug

The following TypeScript code tries to use memoization for Fibonacci but produces wrong output. What is the output when calling fib(4)?

DSA Typescript

function fib(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(4));

A 4

B 5

C undefined

D 3

💡 Hint

Check how memoization cache is checked before recursive calls.

fib(4) = fib(3) + fib(2) = 2 + 1 = 3. The code works correctly and outputs 3.

🚀 Application

advanced

Optimal Substructure in Coin Change Problem

Given unlimited coins of denominations [1, 3, 4], what is the minimum number of coins needed to make amount 6? Use the optimal substructure property.

A 4

B 3

C 2

D 1

💡 Hint

Try to break amount 6 into smaller amounts and combine their solutions.

Minimum coins for 6 is 2: using coins 3 + 3 or 4 + 1 + 1 is more than 2 coins, so 3+3 is optimal.

🧠 Conceptual

expert

Why Dynamic Programming Requires Both Properties

Why does dynamic programming require both overlapping subproblems and optimal substructure properties?

A Because overlapping subproblems allow reuse of solutions and optimal substructure ensures global solution from local solutions

B Because overlapping subproblems guarantee no recursion and optimal substructure guarantees sorting

C Because overlapping subproblems mean problems are independent and optimal substructure means problems are unrelated

D Because overlapping subproblems allow parallel processing and optimal substructure allows random access

💡 Hint

Think about how dynamic programming builds solutions efficiently.

Dynamic programming works by solving smaller overlapping problems once and combining their optimal solutions to solve the bigger problem.