Tabulation (Bottom-Up DP)

Tabulation builds the DP table iteratively starting from base cases, eliminating recursion overhead and stack-depth limits while making memory access patterns cache-friendly.

4 min read Level 3/5 #dsa#dp#tabulation

What you'll learn

Convert a memoized recursive solution into a bottom-up iterative table
Identify why tabulation avoids call-stack overflow for large inputs
Choose between memoization and tabulation based on problem characteristics

Tabulation solves a DP problem by filling an array (or 2-D table) from the smallest subproblems upward, visiting every state in a deliberate order so that when you compute dp[i], all values it depends on are already filled in.

The Pattern

Allocate a table of the right size and type.
Initialize base cases directly in the table.
Loop in dependency order (usually smallest to largest index).
Return the cell that corresponds to the original problem.

function fibTab(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(fibTab(50)); // 12586269025

No recursion, no call-stack risk, and modern JS engines vectorize simple array loops efficiently.

Converting Memoization to Tabulation

The grid path-counting problem from the previous lesson maps directly to a 2-D table:

function uniquePaths(m, n) {
  // dp[r][c] = number of paths to reach row r, col c
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  // Base cases: first row and first column are all 1 (only one path)

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}

console.log(uniquePaths(3, 7)); // 28

Memoization vs Tabulation

Concern	Memoization	Tabulation
Style	Recursive, top-down	Iterative, bottom-up
Stack risk	Yes (deep recursion)	No
Lazy evaluation	Yes (unreached states skipped)	No (all states computed)
Cache-friendliness	Depends on access pattern	Usually sequential
Easier to write first?	Often yes	Requires knowing fill order

Choose tabulation when n is large (stack overflow risk), when you need to squeeze out every millisecond, or when the fill order is obvious. Stick with memoization when only a sparse subset of states is ever reached.

Time and Space

Tabulation for a 1-D problem of size n is O(n) time and O(n) space. The space often reduces further with a rolling-variable trick, which the next lesson covers in detail.

Up Next

Apply both approaches to classic 1-D DP problems and see how rolling variables reduce space to O(1).

1-D Dynamic Programming →