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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Tabulation

What is the output of the following JavaScript code that uses bottom-up tabulation to find the 6th Fibonacci number?

DSA Javascript

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

A 5

B 13

C 8

D 21

💡 Hint

Remember Fibonacci sequence starts with 0, 1 and each next number is sum of previous two.

The Fibonacci sequence starts 0,1,1,2,3,5,8,... The 6th index (0-based) is 8.

❓ Predict Output

intermediate

Count Ways to Climb Stairs

What does this code print? It counts ways to climb 4 stairs taking 1 or 2 steps at a time using bottom-up DP.

DSA Javascript

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

A 5

B 7

C 4

D 6

💡 Hint

Think of ways to reach step i from i-1 and i-2.

Ways to climb 4 stairs are 5: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2).

🔧 Debug

advanced

Identify the Error in Tabulation Code

What error will this code produce when run? It tries to find minimum coins for amount 5 with coins [1,3,4].

DSA Javascript

function minCoins(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(minCoins([1,3,4], 5));

A 2

B SyntaxError

C Infinity

D -1

💡 Hint

Check how dp array updates for amount 5.

Minimum coins for 5 are 2 (4 + 1). The code runs fine and returns 2.

❓ Predict Output

advanced

Longest Increasing Subsequence Length

What is the output of this code that finds length of longest increasing subsequence using bottom-up DP?

DSA Javascript

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}
console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));

A 5

B 6

C 3

D 4

💡 Hint

Longest increasing subsequence is a sequence where each number is bigger than previous.

The longest increasing subsequence is [2,3,7,101] or [2,3,7,18] with length 4. The code returns 4.

❓ Predict Output

expert

Number of Unique Paths in Grid

What is the output of this code that calculates number of unique paths from top-left to bottom-right in a 3x3 grid using bottom-up DP?

DSA Javascript

function uniquePaths(m, n) {
  const dp = Array(m).fill(null).map(() => Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}
console.log(uniquePaths(3, 3));

A 9

B 6

C 3

D 12

💡 Hint

Number of ways to reach a cell is sum of ways from top and left cells.

For 3x3 grid, unique paths count is 6.

Practice

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

easy

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

B. Solve the problem by recursion without storing results

C. Use random guesses to find the solution

D. Start solving from the biggest problem and break it down

Solution

1. Step 1: Understand bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems to bigger ones.

2. Step 2: Compare with other methods

   Unlike recursion without storage, tabulation avoids repeated work by storing results in a table.

3. Final Answer:

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

4. Quick Check:

   Tabulation = Bottom-up table filling [OK]

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

Common Mistakes:

• Confusing tabulation with recursion without memo
• Thinking tabulation starts from the biggest problem
• Ignoring the use of a table to store results

2. Which of the following is the correct way to initialize a tabulation array for Fibonacci numbers in JavaScript?

easy

A. const dp = [];

B. const dp = [0, 1];

C. const dp = [0, 0];

D. const dp = [1, 1];

Solution

1. Step 1: Recall Fibonacci base cases

   Fibonacci sequence starts with 0 and 1, so dp[0] = 0 and dp[1] = 1.

2. Step 2: Check initialization options

   Only const dp = [0, 1]; correctly sets dp = [0, 1] matching Fibonacci base values.

3. Final Answer:

   const dp = [0, 1]; -> Option B

4. Quick Check:

   Fibonacci base = [0,1] [OK]

Hint: Start dp with first two Fibonacci numbers [OK]

Common Mistakes:

• Starting dp with [1,1] which is incorrect base
• Initializing dp with zeros only
• Leaving dp empty without base values

3. What will be the output of the following JavaScript code using bottom-up DP to find Fibonacci number at position 5?

function fib(n) {
  const dp = [0, 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. 8

C. 5

D. 13

Solution

1. Step 1: Trace dp array filling

   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 C

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing index with Fibonacci value
• Returning dp[n-1] instead of dp[n]
• Starting dp with wrong base values

4. Find the error in this bottom-up DP code for Fibonacci numbers:

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

medium

A. dp[i - 2] causes out-of-bound error

B. dp array is not initialized

C. Return statement is missing

D. Loop starts at 1 instead of 2

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but dp[1] is already initialized; calculation should start at i=2.

2. Step 2: Identify impact of wrong loop start

   At i=1, dp[1] = dp[0] + dp[-1] causes dp[-1] undefined, leading to NaN.

3. Final Answer:

   Loop starts at 1 instead of 2 -> Option D

4. Quick Check:

   Loop must start at 2 to avoid invalid index [OK]

Hint: Start loop at 2 to avoid negative index [OK]

Common Mistakes:

• Starting loop at 1 causing invalid dp[-1]
• Ignoring dp initialization
• Assuming dp[-1] is zero

5. Given the problem to find the minimum number of coins to make amount 7 using coins [1, 3, 4], which bottom-up DP table entry represents the minimum coins needed for amount 5?
Assuming dp[0] = 0 and dp[i] = Infinity initially for i > 0, what is dp[5] after filling the table?

hard

A. 2

B. 3

C. 1

D. Infinity

Solution

1. Step 1: Fill dp table for amounts up to 5

   dp[0]=0; dp[1]=1 (1 coin of 1); dp[2]=2 (1+1); dp[3]=1 (coin 3); dp[4]=1 (coin 4); dp[5]=min(dp[5-1], dp[5-3], dp[5-4]) +1 = min(dp[4], dp[2], dp[1]) +1 = min(1,2,1)+1=2.

2. Step 2: Confirm dp[5] value

   Minimum coins for amount 5 is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   dp[5] = 2 coins [OK]

Hint: Check all coin options and pick minimum +1 [OK]

Common Mistakes:

• Not considering all coin choices for dp[i]
• Using wrong initial dp values
• Confusing amount with coin count