cf.completefrontend
DYNAMIC PROGRAMMING · FOUNDATION

Tabulation (bottom-up DP)

Fill a table of answers with a loop, smallest questions first, so every answer you need is already there.

Time O(n)Space O(n)4 practice problemsStep-through picture

The idea

Tabulation is dynamic programming with a loop and a table. You make an array where each cell answers one small question. You fill the cells in order, starting with the smallest questions, and each new cell is computed from cells that are already filled.

This is called bottom-up, because you start from the smallest cases at the bottom and work up to the big question. There is no recursion, so there is no risk of running out of call stack, and loops are usually a bit faster than function calls.

The hard part is choosing the order. Before you fill a cell, every cell it reads must already be filled. For a 1-D table that is usually left to right. For a 2-D table it is usually row by row.

An everyday example

Filling in a times table

When children fill in a times table on paper, they fill row after row, and each row helps with the next. The 7 times row is easy if you add 7 to the cell on its left. Nobody jumps to the bottom-right corner first. Every cell uses cells that are already written, and the last cell holds the answer you wanted.

How the example maps to the code
In the exampleIn the code
The paper gridThe best array
One box on the gridbest[i], the cheapest cost to stand on step i
Filling boxes in reading orderfor (let i = 2; i <= n; i++)
Using boxes already writtenbest[i - 1] and best[i - 2]
The last boxreturn best[n]

From the slow way to tabulation (bottom-up dp)

  1. Start from the recursive idea. The cheapest way to stand on step i is the cheaper of two last jumps: from step i - 1 after paying cost[i - 1], or from step i - 2 after paying cost[i - 2]. Written as plain recursion, this asks the same questions again and again, and the number of calls roughly doubles with each extra step.
  2. Memoization fixes the repeats: store each answer and look it up next time. But the first call is for the top step, and it has to recurse all the way down to step 0 before anything returns. For a staircase of 100,000 steps that is 100,000 nested calls, far past the roughly ten thousand that JavaScript engines allow.
  3. Look at which way the questions point. Step i only ever asks about steps i - 1 and i - 2, which are smaller. So the recursion is only finding its way down to step 0 so it can start answering upward. You already know where the bottom is, so you can start there yourself.
  4. Make an array best with one cell per step. Fill the cells you know without work, then walk i upward from 2. When you reach a cell, the two cells it reads are already filled, so each cell is two additions and a comparison. No call stack is used at all. That loop is tabulation.

How it works

  1. Decide what one cell means. Here best[i] is the cheapest total cost to stand on step i. The top of the stairs is step n, just past the last step.
  2. Create the table with one cell per state: best has n + 1 cells.
  3. Fill the base cases. You may start on step 0 or step 1 for free, so best[0] and best[1] are 0.
  4. Loop i from 2 up to n, so best[i - 1] and best[i - 2] are always ready.
  5. For each i, compute both ways in: from one step below, paying cost[i - 1], or from two steps below, paying cost[i - 2]. Keep the smaller.
  6. Return best[n], the cell for the top.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function cheapestClimb(cost) {
  2. const n = cost.length;
  3. const best = new Array(n + 1).fill(0);
  4. for (let i = 2; i <= n; i++) {
  5. const fromOneBelow = best[i - 1] + cost[i - 1];
  6. const fromTwoBelow = best[i - 2] + cost[i - 2];
  7. best[i] = Math.min(fromOneBelow, fromTwoBelow);
  8. }
  9. return best[n];
  10. }

How fast it is

TimeO(n)
Extra memoryO(n)

One pass over n + 1 cells, each with two additions and a comparison. The table keeps one number per cell; keeping only the last two cells would make it O(1).

  • Best caseO(1)

    cost has 0 or 1 steps. The loop starts at i = 2, which is already past n, so nothing is filled and best[n] is 0.

  • Average caseO(n)

    Any longer staircase: the loop fills each of the n - 1 cells from 2 to n once.

  • Worst caseO(n)

    The same as the average. The costs can't make a cell do more than two additions and a comparison.

Common mistakes

  • Making the table one cell too short, so the top of the stairs (best[n]) does not exist. Count the states carefully, including the final one.
  • Filling cells in an order where a cell reads something not yet computed. Check which cells the transition reads and loop so they come first.
  • Starting the loop at 0 and reading best[-1], which is undefined in JavaScript and turns every sum into NaN. Start after the base cases.
  • Leaving base cells at a default that does not match their meaning, such as 0 where the cost of an impossible state should be Infinity.

When to use it

Look for these clues in a problem:

  • You know the recurrence and every state depends on smaller states in a clear order.
  • The input is large, so recursion would go thousands of calls deep.
  • Most states will be needed anyway, so filling the whole table wastes nothing.
  • You want to shrink memory later by keeping only the last row or last few cells.

Check yourself

Answer each one in your head first, then open it.

Why does the loop start at i = 2 and not at i = 0?

Cells 0 and 1 are base cases that are already right. Starting at 0 would read best[-1] and best[-2], which are undefined and turn the sums into NaN.

Why is best sized n + 1 and not n?

The top of the stairs is step n, one past the last priced step. A table of n cells has no cell for it.

In the trace, why is best[3] equal to 2 when cost[2] is 9?

Because the cheapest way onto step 3 jumps over step 2: stand on step 1, pay its 2, and jump two steps. Step 2's cost is never paid.

When could memoization do less work than tabulation?

When the question only reaches a small part of a huge state space. Memoization only solves the states it visits, while tabulation fills every cell in the table.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps this promise: when it is about to fill best[i], the cells best[0] to best[i - 1] already hold the true cheapest cost to stand on each of those steps. The two free starting cells make it true at the beginning.

Filling best[i] keeps the promise. Any route to step i ends with a jump from i - 1 or from i - 2. If the cheapest route comes from i - 1, the part of it before that jump must be a cheapest route to i - 1; otherwise you could swap in a cheaper one and beat the cheapest route, which is impossible. That is optimal substructure. So the true answer is one of the two values the code compares, and Math.min picks it.

The order is the key choice in tabulation. Every cell reads only smaller indexes, so filling from left to right always reads finished cells. The loop runs once per step from 2 to n and then stops, and the promise at that point says best[n] is the cheapest cost to reach the top.

Going deeper

3 more ideas

Why the order matters

A cell is computed from other cells, so those cells must be final when it reads them. In this table, best[i] reads best[i - 1] and best[i - 2]. Going from left to right guarantees both are done. If you looped from right to left, you would read zeros that were never filled and get wrong answers without any error.

How much work tabulation does

The loop visits each cell once and does a fixed amount of work there, so the time is O(n). The table holds n + 1 numbers. Since each cell only reads the two before it, you could keep just two variables and use O(1) space.

Tabulation versus memoization

Memoization only solves the states the big question reaches, but it uses recursion. Tabulation solves every state in the table, but with a simple loop. When nearly every state is needed, which is common, tabulation is usually faster and safer. When only a few states are reachable out of a huge number, memoization does less work.

Work it by hand

Every step in a table, with why

Find the cheapest way to the top of a staircase with 6 priced steps. Each row fills one cell of best.

cost = [6, 2, 9, 3, 4, 8], so the top is step 6

StepifromOneBelowfromTwoBelowbest[i]What happensWhy
10 and 1--0 and 0Base cells, free startsThe table is made with 0 in every cell. You may start on step 0 or step 1 for free, so those two cells are already right.
220 + 2 = 20 + 6 = 62From one below winsStanding on step 1 and paying its 2 is cheaper than standing on step 0 and paying its 6.
332 + 9 = 110 + 2 = 22From two below winsStep 2 is expensive to leave, so it is cheaper to jump from step 1 straight to step 3.
442 + 3 = 52 + 9 = 115From one below winsBoth cells it reads were filled in earlier rows. Leaving step 3 costs only 3.
555 + 4 = 92 + 3 = 55From two below winsA jump from step 3 reaches step 5 for 5, the same total as reaching step 4.
665 + 8 = 135 + 4 = 99From two below; loop endsi equals n, so this is the top and the last cell. Line 9 returns best[6].

It returns 9: start on step 1 and pay 2, jump to step 3 and pay 3, move to step 4 and pay 4, then jump to the top. The loop ends because i has passed n, so every cell is filled.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Tabulation (bottom-up DP)O(n)O(n)The default when nearly every state is needed: a simple loop with no recursion limit.
MemoizationO(n)O(n)When the recursive version is easier to write, the chain of states is short, or only a few states are reachable from the question.
Two rolling variablesO(n)O(1)When you only need the final number and the cells only look back a fixed distance.
Plain recursionO(2^n)O(n)Only to find and test the recurrence on tiny inputs.

Extra memory: O(n) for the n + 1 cells of best. Each cell only reads the two before it, so two variables would do, which gives O(1).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Tabulation (bottom-up DP) and the other approaches, on a scale where each line up is 10 times more steps.
  • Tabulation (bottom-up DP), Memoization, Two rolling variables O(n)
  • Plain recursion O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Tabulation (bottom-up DP)101,0001 million
Memoization101,0001 million
Two rolling variables101,0001 million
Plain recursion1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
An empty staircase: cost = []
n is 0, best is [0], the loop never runs, and it returns 0. You are already at the top.
One step: cost = [5]
The top is step 1, a free starting point, so it returns 0 without paying anything.
Two steps: cost = [5, 7]
The loop runs once for i = 2 and picks the cheaper of 7 and 5, so it returns 5: start on step 0, pay 5, and jump to the top.
A step that can't be used, written as Infinity
Math.min just avoids it, since any route through it costs Infinity. If every route is blocked, the answer is Infinity, which you may want to turn into -1.
100,000 steps
The loop handles it with no stack use at all. The same input would overflow the call stack in a memoized recursive version.

Variations and follow-ups

Twists interviewers add

Pull versus push

This code pulls: each cell reads the cells it depends on. You can also push: from each filled cell i, update best[i + 1] and best[i + 2] with Math.min. Both fill the same table. Pushing is handy when it's easier to list where a state leads than where it came from.

Rebuilding the route

Keep a second array from, where from[i] records whether the winner came from i - 1 or i - 2. After the loop, start at n and follow from back to step 0 or 1 to list the steps you stood on.

Tables in more dimensions

The same method fills 2-D tables, such as grid DP or the knapsack, usually row by row. The only rule is the same one: before you fill a cell, every cell it reads must be filled. For interval DP, that order is by interval length instead of by row.

Order from a graph

When the states don't line up by index, picture each state as a node with arrows to the states it reads. Any order that puts every arrow's target first works. That is a topological order of the graph, and it exists as long as no state depends on itself.

In an interview

Spot it, explain it, answer follow-ups
  • Reach for it after you have a recurrence: if you can say what each state depends on and all those states are "smaller" in a clear order, you can fill a table in that order.
  • Explain it in four parts: what one cell means, the base cells, the loop order and why it is safe, and which cell holds the answer. Interviewers listen for the order argument.
  • Test it by filling the table by hand for a tiny input, such as cost = [5, 7], and say each cell out loud. Then try [] and [5] to check the base cells and the table size.
  • Expect "can you do it in O(1) space?". Keep two variables for the last two cells and shift them each loop, because no cell reads anything older.

Where frontend code uses it

The same idea in real UI code
  • A spreadsheet-style table in a dashboard where each total cell is computed from the cells above it is a table filled in dependency order.
  • Build tools process modules in an order where every dependency is handled before the modules that import it, the same "inputs first" rule tabulation follows.
  • Precomputing a lookup table once, such as easing values for an animation at each frame, then reading from it later is tabulation.

Related algorithms