Fibonacci Using DP in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci DP with Memoization

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

DSA Typescript

function fib(n: number, memo: 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(7));

A 13

B 34

C 8

D 21

💡 Hint

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

fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8, fib(7)=13. The code returns fib(7) = fib(6) + fib(5) = 8 + 5 = 13.

❓ Predict Output

intermediate

Output of Fibonacci DP with Tabulation

What is the output of this TypeScript code that calculates Fibonacci numbers using tabulation (bottom-up approach)?

DSA Typescript

function fib(n: number): number {
  const dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
console.log(fib(5));

A 8

B 3

C 5

D 13

💡 Hint

The Fibonacci sequence starts 0, 1, 1, 2, 3, 5, 8...

fib(5) is the 5th Fibonacci number starting from 0 index: 0,1,1,2,3,5 so fib(5) = 5.

🧠 Conceptual

advanced

Why use Dynamic Programming for Fibonacci?

Why is dynamic programming a better approach than simple recursion for calculating Fibonacci numbers?

A It avoids repeated calculations by storing intermediate results.

B It uses less memory by not storing any results.

C It calculates Fibonacci numbers using random guesses.

D It only works for small Fibonacci numbers.

💡 Hint

Think about how recursion repeats work for the same inputs.

Dynamic programming stores results of subproblems to avoid recalculating them, making the process efficient.

🔧 Debug

advanced

Identify the error in Fibonacci DP code

What error will this TypeScript code produce when calculating Fibonacci numbers using memoization?

DSA Typescript

function fib(n: number, memo: 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(0));

A Returns undefined

B Returns 0 correctly

C Stack overflow error

D Returns 1 incorrectly

💡 Hint

Check how memo[n] is checked before returning.

The code returns 0 correctly for fib(0) because the base case `if (n <= 1)` is checked before the memo check. However, the memo check `if (memo[n])` uses truthiness, which treats 0 as falsy and would fail if 0 were memoized. Base cases also aren't stored in memo.

🚀 Application

expert

Calculate large Fibonacci number efficiently

Which approach is best to calculate the 50th Fibonacci number efficiently in TypeScript?

A Using a for loop with repeated addition without storing previous results

B Recursion with memoization (top-down DP)

C Simple recursion without memoization

D Iterative tabulation (bottom-up DP)

💡 Hint

Consider time and space efficiency for large inputs.

Iterative tabulation uses a simple loop and stores only needed values, making it faster and more memory efficient than recursion with memoization for large n.