Memoization Top Down DP 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 uses memoization to compute Fibonacci numbers?

DSA Typescript

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

A 13

B 21

C 5

D 8

💡 Hint

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

The function computes Fibonacci numbers using memoization. fib(6) returns the 6th Fibonacci number which is 8.

❓ Predict Output

intermediate

Output of Climbing Stairs Problem with Memoization

What is the output of this TypeScript code that counts ways to climb stairs using memoization?

DSA Typescript

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

A 5

B 13

C 8

D 10

💡 Hint

Think of ways to reach step 5 by 1 or 2 steps from previous steps.

The function counts ways to climb stairs with 1 or 2 steps. climbStairs(5) = 8 ways.

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

What error will this TypeScript code produce when run?

DSA Typescript

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

A Stack overflow error

B Returns -1

C Returns 0

D Returns undefined

💡 Hint

What happens if input is negative and base case only handles n <= 1?

No error occurs. The base case n <= 1 returns n directly for negative inputs like -1.

🧠 Conceptual

advanced

Memoization Cache Size for Staircase Problem

If you run the memoized climbStairs function for n=10, how many entries will be stored in the memo cache after the call completes?

DSA Typescript

function climbStairs(n: number, memo: Record<number, number> = {}): number {
  if (n <= 2) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
  return memo[n];
}
climbStairs(10);

A 8

B 9

C 10

D 11

💡 Hint

Memo stores results for each unique n from 3 to 10.

Memo cache stores results for n=3 to n=10, total 8 entries. Base cases are returned directly without memo storage.

🚀 Application

expert

Output of Memoized Coin Change Ways Count

What is the output of this TypeScript code that counts ways to make change using memoization?

DSA Typescript

function countWays(coins: number[], amount: number, index = 0, memo: Record<string, number> = {}): number {
  const key = amount + ',' + index;
  if (amount === 0) return 1;
  if (amount < 0 || index === coins.length) return 0;
  if (memo[key] !== undefined) return memo[key];
  memo[key] = countWays(coins, amount - coins[index], index, memo) + countWays(coins, amount, index + 1, memo);
  return memo[key];
}
console.log(countWays([1, 2, 5], 5));

A 4

B 6

C 3

D 5

💡 Hint

Count all combinations of coins that sum to 5.

The function counts ways to make amount 5 using coins 1,2,5. The answer is 4 ways.