What Is Tabulation? Filling a Dynamic-Programming Table Upward

Tabulation is the loop form of dynamic programming. You fill a table from the smallest sizes to the one the question asked for. Memoisation is the other repair: a recursive call checks a cache before it repeats work. Both store overlapping answers. The loop makes the order obvious.

How it works

Write a sentence for the cell before you write the assignment. For Fibonacci, the cell is the sum of the two previous cells, with 0 and 1 as the base cases in the table-filling lesson. Two variables are enough if you never need the whole table again. That is O(n) time and O(1) extra memory.

House robber is the same shape with a choice. At each house you skip it and keep the previous answer, or you take it and add it to the answer from two houses ago. The cell is the better of those two. Adjacent houses are never both taken. An empty street is 0.

Use prefix lengths to keep indexes precise. Let best(i) mean the maximum loot among the first i houses:

• best(0) = 0
• best(1) = houses[0]
• best(i) = max(best(i - 1), best(i - 2) + houses[i - 1])

State i is a count, so the current array index is i - 1. The first recurrence branch skips that house. The second takes it, so the previous house must be excluded and the compatible prefix ends two states back.

Climbing stairs used a close recurrence, with different base cases. Mixing those base cases is how a correct loop returns the wrong number.

ThemeKiln

Terminal

Press Run to execute this example. Use console.log to print a value.

ResetRun

Expected output: 12, then 0. The best choice takes houses worth 2, 9, and 1; no two are adjacent.

Worked example

The best totals after each house are 2, 7, 11, 11, and 12. At the house worth 9, taking gives 2 + 9 = 11 and skipping gives 7. At the house worth 3, taking gives 7 + 3 = 10, so skipping preserves 11.

Why it is correct

After processing each house, oneBack is the best legal total for the prefix ending there, and twoBack is the best total for the prefix before the previous house. An optimal solution either skips the current house and keeps oneBack, or takes it and must add its value to twoBack. Those cases are exhaustive and disjoint, so their maximum is the optimal value for the new prefix.

Cost

The loop processes each house once, for O(n) time. Two accumulated states replace an O(n) table, so auxiliary space is O(1). If the actual chosen house indexes are required, keep the table and reconstruct the decisions, trading O(n) space for that information.

In the course

Dynamic programming introduces the recurrence, memoisation, and the upward loop on the stairs. The next lesson fills Fibonacci from the bottom and then the line of houses. If you can say what the cell means, the assignment is mechanical.

Common mistakes

Using the stair base cases, where the first two answers are 1 and 2, for a Fibonacci that wants 0 and 1.

Taking every other house from the first house only. The better total sometimes starts on the second house. The recurrence already considers both.

Leaving the recursion uncached and calling it tabulation. The cache and the loop are both dynamic programming. This lesson wants the loop.

When to use it

Use tabulation when the recurrence is clear and the states have a natural order, from small to large. It is usually the version you keep once you trust the sentence for the cell.

When not to

Do not build a table for a problem whose subproblems do not overlap. A plain recursion, or a single pass, is then the shorter program.

Problem-solving checklist

Write exactly what one state means before writing its recurrence. List base cases from that meaning, not from a similar problem. For each transition, name every legal choice and the smaller state it uses. Test empty, one-state, and two-state inputs before a longer example.

Optional enrichment

Return both the maximum loot and the chosen house indexes. A scalar recurrence is no longer enough for reconstruction, so decide what additional decision information each state must retain.