DP Table Builder - Dynamic Programming Practice
Using coins [1, 2, 5] (unlimited supply), what's the fewest coins that make exactly 9?
What is min(1)?
The base cases are given. Every other cell follows from the recurrence - one cell at a time, left to right.
The recurrence alone is exponential - it recomputes the same subproblems over and over. Filling them left to right, once each, is the whole of dynamic programming. Reading a filled table backwards is how you recover the choices that produced the answer.
About DP Table Builder
Fill a dynamic-programming memo table cell by cell, from given base cases and a stated recurrence, until the final answer falls out.
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.
Why quant 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.
The DP Table Builder guide covers how scoring works, the strategy that wins, a worked example and the mistakes most players make.
More Algorithms games
- Mini Task - Rookie - A rookie-level coding challenge: two warm-up questions, real code run against real tests in your browser, then two wrap-up questions.
- Monte Carlo Estimator - Estimate pi by throwing random points at a circle, watch the error shrink with sample size, and internalize why halving the error always costs four times the samples.
- Speed Round - Ten multiple-choice questions, twenty seconds each, drawn from a shuffled pool spanning complexity, dynamic programming, Monte Carlo, and pandas.
- All Algorithms practice
- Every game guide