Tabulation is the bottom-up approach to Dynamic Programming. Instead of starting from the top and recursing down, you start from the smallest subproblems and build your way up to the answer. No recursion needed.
Think of it like building a house — you start with the foundation, then the walls, then the roof. You would not try to install the roof first and then figure out what walls you need. That is the bottom-up mindset.
Fibonacci with Tabulation
With tabulation, we fill a table (usually an array) from the base cases upward. Each entry depends only on entries we have already computed.
function fib(n) {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 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(10));
console.log(fib(50));We start with the known values — fib(0) is 0 and fib(1) is 1 — and fill the array one cell at a time. By the time we reach dp[n], every value it depends on is already sitting right there in the array.
Memoization vs Tabulation
Both approaches give the same time and space complexity. The key difference is style. Memoization is top-down — you start from the big problem and break it down. Tabulation is bottom-up — you start from the smallest pieces and build up.
Tabulation avoids the overhead of recursion, so it is often faster in practice. It also does not risk stack overflow. On the other hand, memoization can be easier to implement when the subproblem graph is irregular or you only need a subset of all possible subproblems.
Space Optimization
One neat trick with tabulation is that you can often reduce space usage. In Fibonacci, we only ever look at the previous two values, so we do not need the whole array — just two variables. This cuts space from O(n) down to O(1).
Not every DP problem allows this, but when it does, it is worth doing. Always ask yourself "which previous values do I actually need right now?" before allocating a giant table.