DP Table Builder

How it works

Each round generates one of three puzzle types with random parameters: Staircase Climb (how many ways to climb n stairs taking 1 or 2 steps, n between 6 and 10), House Robber (maximize loot from 6 to 9 houses with random values 2 to 15, no two adjacent), or Coin Change (fewest coins to make a target of 7 to 13 from a set that always includes a 1-coin). The prompt, the recurrence, and the table layout are shown on screen.

The table's base cases come pre-filled - two cells for staircase and house robber, one cell (min(0) = 0) for coin change. You fill the remaining cells strictly left to right, one at a time: type a number for the highlighted cell and press Fill cell or Enter. Whether you were right or wrong, the correct value is written into the cell and the highlight moves on, so the table you build from is always correct.

When the last cell is filled, the round ends and the final answer is read off the last cell of the table. Next puzzle starts a fresh random round and resets the score.

How scoring works

You score 1 point per cell answered correctly on the first try. There are no retries on a cell - a wrong entry is marked wrong, the correct value is filled in, and play moves to the next cell.

The completion screen reports your score out of the number of fillable cells (table length minus base cases) and states the final answer. A perfect round is every fillable cell right first try.

Every table value is computed by running the displayed recurrence in code, not hand-authored, so the answer key cannot disagree with the recurrence you are shown.

Read the recurrence as an instruction, not a formula

The recurrence on screen tells you exactly which already-filled cells feed the current one. ways(n) = ways(n-1) + ways(n-2) means: look one cell left, look two cells left, add. best(i) = max(best(i-1), best(i-2) + value[i]) means: compare skipping this house against taking it plus the best from two back. You never need to re-derive the logic - you need to execute it without arithmetic slips.

This is the core discipline of bottom-up DP: once base cases and a recurrence are fixed, filling the table is mechanical. Interviewers who ask you to trace a DP table are checking whether you actually understand what each cell means, because the mechanical part exposes anyone who memorized the recurrence without knowing what its arguments refer to.

Because wrong answers are corrected in place, one slip never cascades. Use that: if a cell surprises you, look at the corrected value, work out which input you misread, and fix the habit before the next cell rather than after the round.

Know the three recurrences cold

Staircase is Fibonacci in disguise: with ways(0) = 1 and ways(1) = 1 the table runs 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. If you recognize this on round one, staircase rounds become pure speed - you can fill an n = 10 table from memory and only sanity-check the addition.

House Robber requires actually reading the values array, since it is regenerated every round. The two candidates for each cell are best(i-1), meaning skip house i, and best(i-2) + value[i], meaning rob it. A useful check: the table is non-decreasing, because skipping is always available. If your candidate value ever drops below the previous cell, you made an error.

Coin Change is the only minimization: min(amt) = 1 + the smallest min(amt - c) over coins c that fit. Since every coin set contains a 1, min(amt) is at most min(amt-1) + 1, and consecutive cells differ by at most 1 - min values only ever step up by one or drop. Scan all coins for each cell; the biggest usable coin is often, but not always, the best one, which is exactly the greedy trap the puzzle is built on.

Build a per-cell routine

Accuracy under repetition comes from a fixed routine, not fresh thought per cell. For each cell: identify the one or few source cells the recurrence names, read their values from the table (they are all visible and guaranteed correct), apply the operation, and type. Resist doing two cells of arithmetic in your head at once - the game only ever asks for one cell, so keep the working set to one cell.

The most common failure mode is an index slip: reading value[i-1] when the recurrence says value[i], or mixing up which house label the current cell corresponds to. Cell labels like best(4) are printed under every cell - anchor on the label, then find position 4 in the values list in the prompt, before touching the recurrence.

A worked example

Round: House Robber with 6 houses holding [4, 11, 3, 9, 6, 12]. Base cases given: best(0) = 4 (only house 0 exists) and best(1) = max(4, 11) = 11.

best(2): max(best(1), best(0) + value[2]) = max(11, 4 + 3) = 11 - robbing house 2 is not worth giving up house 1. best(3): max(11, 11 + 9) = 20 - best(1) did not use house 2, so house 3 stacks on it. best(4): max(20, 11 + 6) = 20. best(5): max(20, 20 + 12) = 32.

The table completes as [4, 11, 11, 20, 20, 32], final answer 32, and if all four fillable cells were right first try the score reads 4/4. Notice the flat stretches - best(2) = best(1) and best(4) = best(3) - those are the cells where skipping wins, and they are where a greedy taker goes wrong.

Common mistakes

• Applying the recurrence to the wrong cells - off-by-one on i-1 versus i-2 is the single most common wrong entry. Anchor on the printed cell label first.

• Playing House Robber greedily - taking every large value. The recurrence exists precisely because the greedy answer is wrong when large values are adjacent.

• In Coin Change, only trying the largest coin. The set [1, 3, 4] making 6 wants 3+3, not 4+1+1 - check every coin for every cell.

• Doing multi-cell arithmetic in your head. The table shows every previous correct value; read from it instead of recomputing.

• Forgetting the staircase base convention ways(0) = 1. The empty climb counts as one way, which is why the table is 1, 1, 2, 3, ... and not 0, 1, ...

Why interviews test this

Tracing a DP table by hand is a standard interview probe because it separates candidates who understand state definitions from those who pattern-match problem names to memorized code. If you can fill best(i) tables quickly and explain what each cell means mid-fill, the harder interview steps - defining the state yourself, writing the recurrence for a novel problem - become the only new work.

Staircase, house robber, and coin change are also three of the most-asked DP screens in their own right, at quant firms and big tech alike, so the specific tables here are directly reusable material.