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.

Practice

1. What is the main idea behind Tabulation Bottom Up DP?

easy

A. Build a table from the smallest subproblems up to the main problem

B. Solve the problem by dividing it into two halves recursively

C. Use recursion with memoization to avoid repeated work

D. Randomly guess answers and check correctness

Solution

1. Step 1: Understand Tabulation approach

   Tabulation means filling a table starting from the smallest subproblems, moving upwards.

2. Step 2: Compare with other methods

   Unlike recursion with memoization, tabulation solves subproblems iteratively in order.

3. Final Answer:

   Build a table from the smallest subproblems up to the main problem -> Option A

4. Quick Check:

   Tabulation = Bottom Up DP [OK]

Hint: Think bottom-up: solve small parts first, then bigger [OK]

Common Mistakes:

• Confusing tabulation with recursion
• Thinking tabulation guesses answers
• Mixing memoization with tabulation

2. Which of the following is the correct TypeScript syntax to initialize a DP array of size n+1 with zeros for tabulation?

easy

A. const dp = new Array(n+1).fill(0);

B. const dp = Array().map(() => 0);

C. const dp = new Array(n).fill(null);

D. const dp = Array.fill(n+1, 0);

Solution

1. Step 1: Check correct array initialization

   Using new Array(n+1).fill(0) creates an array of length n+1 filled with zeros.

2. Step 2: Identify incorrect options

   const dp = Array().map(() => 0); uses map on empty array which won't fill correctly; const dp = new Array(n).fill(null); fills with nulls; const dp = Array.fill(n+1, 0); is invalid syntax.

3. Final Answer:

   const dp = new Array(n+1).fill(0); -> Option A

4. Quick Check:

   Array fill with zeros = new Array(n+1).fill(0) [OK]

Hint: Use new Array(size).fill(value) to initialize arrays [OK]

Common Mistakes:

• Using map on empty array without elements
• Wrong array size (n instead of n+1)
• Using invalid Array.fill syntax

3. What will be the output of the following TypeScript code using bottom-up DP to find the nth Fibonacci number?

function fib(n: number): number {
  const dp = 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(5));

medium

A. 3

B. 5

C. 8

D. 13

Solution

1. Step 1: Trace dp array filling for n=5

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Return dp[5]

   The function returns dp[5] which is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Starting dp[1] as 0 instead of 1
• Off-by-one errors in loop
• Returning dp[n-1] instead of dp[n]

4. Identify the bug in this bottom-up DP code for calculating factorial of n:

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

medium

A. The loop should start from i = 0

B. dp array should be initialized with zeros, not ones

C. The multiplication should be dp[i] = dp[i] * i

D. dp[0] should be set to 1 before the loop

Solution

1. Step 1: Check dp initialization and base case

   dp is filled with 0s, but dp[0] must be explicitly set to 1 as factorial(0)=1.

2. Step 2: Verify loop correctness

   Loop from i=1 to n is correct; dp[i] = dp[i-1] * i is correct formula.

3. Final Answer:

   dp[0] should be set to 1 before the loop -> Option D

4. Quick Check:

   Base case dp[0]=1 needed [OK]

Hint: Always set base case explicitly in DP arrays [OK]

Common Mistakes:

• Starting loop at 0 causing dp[-1] access
• Wrong initialization of dp array
• Incorrect multiplication formula

5. You want to find the minimum number of coins needed to make amount n using coins of denominations [1, 3, 4] with bottom-up DP. Which of these is the correct tabulation approach?

hard

A. Initialize dp array with zeros; for each coin, add 1 to dp[coin] only once

B. Use recursion to try all coin combinations without dp array

C. Initialize dp array with Infinity except dp[0]=0; for each amount i from 1 to n, update dp[i] = min(dp[i], dp[i - coin] + 1) for each coin if i >= coin

D. Initialize dp array with zeros; for each amount i, set dp[i] = dp[i-1] + 1 only

Solution

1. Step 1: Understand coin change tabulation

   We start dp with Infinity except dp[0]=0 because 0 coins needed for amount 0.

2. Step 2: Update dp for each amount and coin

   For each amount i, check all coins; if coin <= i, update dp[i] = min(dp[i], dp[i-coin] + 1).

3. Final Answer:

   Initialize dp array with Infinity except dp[0]=0; for each amount i from 1 to n, update dp[i] = min(dp[i], dp[i - coin] + 1) for each coin if i >= coin -> Option C

4. Quick Check:

   Coin change DP = min coins with dp and Infinity init [OK]

Hint: Use Infinity init and min update for coin change DP [OK]

Common Mistakes:

• Not initializing dp with Infinity
• Ignoring multiple coin options per amount
• Using recursion instead of tabulation