Tabulation (Bottom-Up)

Concept

Tabulation (Bottom-Up DP) is the iterative cousin of Memoization.
Instead of starting at N and recursively plunging down to find the Base Cases, Tabulation explicitly starts at the Base Cases (0 and 1), puts them in an Array (a Table), and uses a simple for loop to build up to N.

There is no Recursion. There is no Call Stack. There is no Hash Map.
It is physically faster in hardware execution speed, but conceptually harder for humans to write, because you must perfectly understand the mathematical iteration sequence of the array.

The Mechanism

Let’s optimize Fibonacci using Tabulation.

// Time Complexity: O(N)
// Space Complexity: O(N) (For the Array)

function fibTab(n: number): number {
    // Handle edge cases
    if (n === 0) return 0;
    if (n === 1) return 1;

    // 1. Create the Table (Array)
    const dp = new Array(n + 1);

    // 2. Initialize the Base Cases
    dp[0] = 0;
    dp[1] = 1;

    // 3. Build up to N using the Recurrence Relation
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 4. The final answer is sitting exactly at index N!
    return dp[n];
}

State Reduction Optimization ($O(1)$ Space)

Tabulation unlocks a magical superpower that Memoization physically cannot achieve: State Reduction.

Look at the for loop in Tabulation:
dp[i] = dp[i - 1] + dp[i - 2];

To calculate dp[10], we ONLY need the values of dp[9] and dp[8].
We absolutely do not care about dp[7], dp[6], or dp[0]. They are mathematically dead to us.
But our massive dp array is storing all of them in RAM! This takes $O(N)$ space.

We can completely delete the Array. We just need two variables to track the “Previous” and “Two Previous” values. As the loop progresses, we physically slide the variables forward.

// Time Complexity: O(N)
// Space Complexity: O(1) (PURE PERFECTION)

function fibOptimized(n: number): number {
    if (n === 0) return 0;

    let twoBack = 0; // dp[i-2]
    let oneBack = 1; // dp[i-1]

    for (let i = 2; i <= n; i++) {
        // Calculate the current step
        const current = twoBack + oneBack;
        
        // Slide the window forward for the next iteration!
        twoBack = oneBack;
        oneBack = current;
    }

    return oneBack;
}

This is the absolute pinnacle of Dynamic Programming. We achieved $O(N)$ time with $O(1)$ space.
(Note: You can ONLY do State Reduction if the Recurrence Relation only looks back a fixed number of steps. If dp[i] requires looking back at ALL previous elements dp[0...i-1], you are forced to keep the full Array).

Interview Strategy

1. If you are struggling in an interview, start with Memoization. Write a naive recursive function, and just slap a Hash Map onto it. It proves you understand DP and will pass 90% of test cases.
2. If you want to impress the interviewer, explicitly rewrite it into Tabulation using a dp Array.
3. For a Senior-level flex, look at your dp Array. If it only looks back 1 or 2 steps, delete the array and write the State Reduction version, explicitly explaining how you achieved $O(1)$ space complexity.

Interview Questions

Q: I have a 2D Tabulation grid: dp = new Array(rows).fill(new Array(cols).fill(0)). Why is this causing bizarre bugs?
A: This is a notorious JavaScript array initialization trap. new Array(cols).fill(0) creates ONE physical array in memory. The .fill() method then places a reference to that exact same physical array into every single row. If you modify dp[0][5] = 99, you will instantly see 99 appear in row 1, row 2, and row 3, because they are all pointing to the exact same array in RAM! You MUST use a mapping loop: Array.from({length: rows}, () => new Array(cols).fill(0)).