Tabulation Bottom Up DP in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Tabulation

What is the output of the following TypeScript code that uses bottom-up tabulation to compute Fibonacci numbers?

DSA Typescript

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

A 8

B 13

C 5

D 21

💡 Hint

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

The function calculates Fibonacci numbers using bottom-up tabulation. fib(6) returns the 6th Fibonacci number which is 8.

❓ Predict Output

intermediate

Number of ways to climb stairs

What is the output of this TypeScript code that uses bottom-up DP to count ways to climb 4 stairs taking 1 or 2 steps at a time?

DSA Typescript

function climbStairs(n: number): number {
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    dp[i] += dp[i - 1];
    if (i - 2 >= 0) dp[i] += dp[i - 2];
  }
  return dp[n];
}
console.log(climbStairs(4));

A 6

B 4

C 7

D 5

💡 Hint

Count all ways to reach step 4 by taking 1 or 2 steps.

The dp array counts ways: dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5. So output is 5.

❓ Predict Output

advanced

Coin change number of combinations

What is the output of this TypeScript code that uses bottom-up DP to count the number of ways to make amount 5 using coins [1,2,5]?

DSA Typescript

function coinChange(coins: number[], amount: number): number {
  const dp: number[] = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (let coin of coins) {
    for (let x = coin; x <= amount; x++) {
      dp[x] += dp[x - coin];
    }
  }
  return dp[amount];
}
console.log(coinChange([1, 2, 5], 5));

A TypeError

B 4

C 3

D 5

💡 Hint

Check how dp array updates for each coin and amount.

No error occurs. The code correctly counts combinations (order doesn't matter). After processing coins: dp = [1,1,2,2,3,4]. Output is 4.

❓ Predict Output

advanced

Longest Common Subsequence length

What is the output of this TypeScript code that finds the length of the longest common subsequence of 'abcde' and 'ace' using bottom-up DP?

DSA Typescript

function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}
console.log(lcs('abcde', 'ace'));

A 5

B 2

C 3

D 4

💡 Hint

Longest common subsequence of 'abcde' and 'ace' is 'ace'.

The LCS length is 3 because 'ace' is the longest subsequence common to both strings.

🧠 Conceptual

expert

Why bottom-up DP is preferred over top-down in some cases?

Which of the following is the best reason to prefer bottom-up tabulation over top-down memoization in dynamic programming?

A Bottom-up DP avoids recursion overhead and can be more space efficient.

B Bottom-up DP always uses less memory than top-down memoization.

C Top-down memoization cannot solve overlapping subproblems.

D Bottom-up DP is easier to write and understand for all problems.

💡 Hint

Think about recursion call stack and memory usage.

Bottom-up DP uses loops instead of recursion, avoiding call stack overhead and sometimes reducing space usage by iterative computation.