Tabulation Bottom Up DP in DSA Typescript

Mental Model

Build the answer step-by-step from the smallest parts up, saving each result in a table so you don't repeat work.

Analogy: Like filling a staircase from the bottom step to the top, where each step depends on the steps below it.

Table: [0] [1] [2] [3] [4] [5]
Values:  0   1   1   2   3   5
↑ 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 0 to 5

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

fib: [0, 1, _, _, _, _]

Why: We need starting points to build the rest

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

fib: [0, 1, 1, _, _, _]

Why: Each Fibonacci number depends on the two before it

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

fib: [0, 1, 1, 2, _, _]

Why: Build next value using previous results

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

fib: [0, 1, 1, 2, 3, _]

Why: Continue filling table step by step

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

fib: [0, 1, 1, 2, 3, 5]

Why: Final answer is at the last index

Result:

fib: [0, 1, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA Typescript

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

// Driver code
const n = 5;
console.log(Fibonacci.fib(n));

if (n <= 1) return n;

handle smallest inputs directly

fibTable[0] = 0; // base case

initialize first base case

fibTable[1] = 1; // base case

initialize second base case

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

iterate from smallest subproblem to target

fibTable[i] = fibTable[i - 1] + fibTable[i - 2];

compute current value from previous two

return fibTable[n];

return final computed answer

Output

5

Complexity Analysis

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

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

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 Typescript

if (n <= 1) return n;

n = 1

Returns 1 immediately as base case

DSA Typescript

if (n <= 1) return n;

When to Use This Pattern

When you see a problem asking for a value built from smaller subproblems with overlapping parts, use bottom-up tabulation to build answers from the smallest pieces up.

Common Mistakes

Mistake: Trying to compute the answer recursively without saving results, causing repeated work
Fix: Use a table to save intermediate results and fill it iteratively

Mistake: Not initializing base cases in the table before the loop
Fix: Always set base cases explicitly before building the rest

Summary

It builds the solution from the smallest subproblems up using a table.

Use it when a problem can be broken into smaller overlapping subproblems.

The key is to fill a table step-by-step so you never repeat calculations.