Dynamic Programming: Fill the Table

Solve a big problem by solving small versions first and writing the answers in a table.

The idea (do not redo your homework)

Say you are asked, “how many ways can I climb 30 stairs taking 1 or 2 steps at a time?” Instead of re-counting from scratch, notice: to stand on stair 30 you came from stair 29 or stair 28. So ways(30) = ways(29) + ways(28). If you write each answer in a table the first time you work it out, every later cell is just a quick look-up of cells you already have.

Every DP problem has the same recipe:

  1. State: what does one cell mean? (e.g. “dp[i] = ways to climb i stairs”).
  2. Base cases: the cells you know without thinking.
  3. Transition: a formula that builds a cell from earlier cells. The yellow cells in the picture are exactly the cells the formula reads.
  4. Order: fill so that the cells you need are always ready.
  5. Answer: usually the last cell.

Watch it work

Try it

Common mistakes

Complexity, in plain English: work equals the number of cells, each filled in constant time. Stairs: O(n). LCS: O(m × n). Knapsack: O(items × capacity). The same recursion without a table could be exponentially slower.