What is tabulation in DP?

AlgorithmsJunior~3 min read

Short answer

Tabulation (bottom-up) in dynamic programming is an approach in which we iteratively fill a table (array/matrix) with subproblem values, starting from the base cases and moving toward the answer. The solution is computed without recursion, in a predetermined order, so that each subproblem relies on already-computed smaller ones. This gives predictable complexity O(number of states x number of transitions) and allows memory to be optimized (for example, down to a single row/column).

Detailed breakdown

The idea and the difference from memoization (top-down)

Tabulation (bottom-up): we build the answer from the bottom up. No recursion: we set a traversal order for the states, and each new state relies on already-computed ones.
Memoization (top-down): we use recursion with a cache. States are computed on demand, recursion depth can be a problem, but it's easier to write when the transitions are complex.
When a natural computation order is known and it matters to avoid recursion/the stack, tabulation is preferable.

Key steps of tabulation

Define the DP state (what dp[i], dp[i][j], and so on mean).
Set the storage structure (array/matrix) and its size.
Initialize the base cases (boundary values, zero states).
Determine the correct traversal order so the needed subproblems are already computed.
Write the transition (the formula), walk through all states, and fill the table.
Read the answer from the appropriate cell (usually dp[n], dp[n][m]).

Example 1: Fibonacci - tabulation (O(n) time, O(1) memory)

State: dp[i] is the i-th Fibonacci number; base cases: dp[0]=0, dp[1]=1; order: i from 2 to n.

function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1; // keep only the last two values
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

console.log(fib(10)); // 55

Example 2: Number of ways to make an amount (Coin Change, combinations)

Problem: given an unlimited supply of coins, count the number of ways to make up amount. State: dp[s] is the number of ways to make sum s. Base: dp[0]=1 (one way to make zero: take nothing). Order: outer loop over coins, inner loop over the sum in increasing order, so permutations are not counted as different ways.

function countWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let s = coin; s <= amount; s++) {
      dp[s] += dp[s - coin];
    }
  }
  return dp[amount];
}

console.log(countWays([1, 2, 5], 5)); // 4 (1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

Choosing the traversal order: common patterns

Unbounded items (for example, coin change "number of ways"): outer loop over items, inner loop over "weight/sum" in increasing order.
0/1 knapsack (each item at most once): outer loop over items, inner loop over weight in decreasing order, so an item is not reused within the same iteration.
Two-dimensional DP (LCS, edit distance): fill the matrix by rows/columns, starting from the base row/column.

Memory optimization (rolling array)

If the transition only uses the previous row/column, you only need to store that one. Example: 0/1 knapsack with a single row and a reverse traversal of the weight:

function knap01(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    const w = weights[i], v = values[i];
    for (let cap = W; cap >= w; cap--) {
      dp[cap] = Math.max(dp[cap], dp[cap - w] + v);
    }
  }
  return dp[W];
}

console.log(knap01([2,3,4], [4,5,10], 6)); // 14 (take the items with weights 2 and 4)

Complexity and when to apply it

Time: O(number of states x number of transitions from each state).
Memory: O(number of states), often reduced to O(the size of one layer) with a careful traversal order.
Use it when there is a DAG of subproblems with a natural order, when it's important to avoid recursion, and/or when you need to compute not only the final answer but all intermediate values too.

Common mistakes in tabulation

Incorrect base initialization: dp[0] for "the number of ways" must be 1, not 0.
Wrong traversal order, which leads to using values that are not yet computed, or recomputing states with items reused.
Off-by-one index shifts in 1D/2D arrays.
Confusing minimums/maximums with the number of ways - these need different bases and operations (+, min, max).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.