Tabulation Bottom Up DP in DSA Javascript

Mental Model

Start solving the smallest parts first and build up to the full problem by saving answers in a table.

Analogy: Like filling a staircase from the bottom step by step, so you can reach the top easily without jumping.

Table: [0, 0, 0, 0, 0]
Index:  0  1  2  3  4
↑ Start filling from left to right

Dry Run Walkthrough

Input: Find the 5th Fibonacci number using bottom-up tabulation

Goal: Calculate Fibonacci(5) by filling a table from the smallest values up

Step 1: Initialize table with base cases: fib[0] = 0, fib[1] = 1

Table: [0, 1, 0, 0, 0, 0]
Index:  0  1  2  3  4  5

Why: Base cases are known and needed to build bigger answers

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0 = 1

Table: [0, 1, 1, 0, 0, 0]
Index:  0  1  2  3  4  5

Why: Use previous results to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1 = 2

Table: [0, 1, 1, 2, 0, 0]
Index:  0  1  2  3  4  5

Why: Build on smaller solved parts to get next value

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1 = 3

Table: [0, 1, 1, 2, 3, 0]
Index:  0  1  2  3  4  5

Why: Continue building up using stored answers

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2 = 5

Table: [0, 1, 1, 2, 3, 5]
Index:  0  1  2  3  4  5

Why: Final answer is built from all smaller answers

Result:

Table: [0, 1, 1, 2, 3, 5]
Fibonacci(5) = 5

Annotated Code

DSA Javascript

class Fibonacci {
  static fibTabulation(n) {
    if (n <= 1) return n;
    const fib = new Array(n + 1).fill(0);
    fib[0] = 0; // base case
    fib[1] = 1; // base case
    for (let i = 2; i <= n; i++) {
      fib[i] = fib[i - 1] + fib[i - 2]; // build from smaller subproblems
    }
    return fib[n];
  }
}

// Driver code
const n = 5;
const result = Fibonacci.fibTabulation(n);
console.log(`Fibonacci(${n}) = ${result}`);

if (n <= 1) return n;

handle smallest inputs directly

fib[0] = 0; // base case

initialize first base case

fib[1] = 1; // base case

initialize second base case

for (let i = 2; i <= n; i++) {

iterate from smallest unsolved to target

fib[i] = fib[i - 1] + fib[i - 2]; // build from smaller subproblems

fill current table entry using previous two

return fib[n];

return final answer from table

Output

Fibonacci(5) = 5

Complexity Analysis

Time: O(n) because we fill the table once from 2 to n

Space: O(n) because we store all Fibonacci values up to n in the table

vs Alternative: Compared to naive recursion which is exponential, tabulation is much faster by avoiding repeated work

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Javascript

if (n <= 1) return n;

n = 1

Returns 1 immediately as base case

DSA Javascript

if (n <= 1) return n;

Large n (e.g., 50)

Computes efficiently using table without stack overflow

DSA Javascript

for (let i = 2; i <= n; i++) {

When to Use This Pattern

When you see a problem asking for a value built from smaller subproblems with overlapping parts, reach for bottom-up tabulation to build answers step-by-step efficiently.

Common Mistakes

Mistake: Trying to compute Fibonacci recursively without memoization causing repeated work
Fix: Use a table to store answers from smallest to largest (bottom-up) to avoid repeats

Mistake: Forgetting to initialize base cases in the table
Fix: Always set fib[0] and fib[1] before the loop

Summary

Calculates answers by filling a table from smallest subproblems up to the full problem.

Use when a problem can be broken into smaller overlapping subproblems and you want efficient computation.

The key is to solve and store small parts first, then build bigger answers using those stored results.

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