Dynamic programming: never solve the same question twice

Dynamic programming (DP) is recursion that never answers the same smaller question twice. You write down each smaller answer the first time you work it out. There are two ways. Top-down stores each answer in a cache as you recurse. Bottom-up fills a table from the smallest case upwards.

Think of it like this: counting 1 + 1 + 1 + 1 + 1 + 1 + 1 on paper. If someone then writes “+ 1” at the end, you don't recount from the start. You remember it was 7 and say 8. DP is remembering earlier answers instead of recounting them.

How to spot it

Words and constraints in a problem that point to this pattern:

• “How many ways…” to climb, decode, reach or make change
• “Minimum or maximum cost, profit or number of steps” where each choice affects the choices after it
• “Can you reach / make / form…?” with a take-it-or-skip-it choice at each step
• Two strings and “longest common…” or “fewest edits”: a 2D table
• Your recursive solution gives the right answers but times out

Watch it work

The template

// 1. State:      dp[i] = fib(i)
// 2. Recurrence: dp[i] = dp[i - 1] + dp[i - 2]
// 3. Base cases: dp[0] = 0, dp[1] = 1
// 4. Order:      i from 2 up to n, so both cells it reads are ready
// 5. Answer:     dp[n]

// Top-down: the plain recursion plus a cache.
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) return n;                  // base cases
  if (memo.has(n)) return memo.get(n)!;  // asked before: answer from the cache
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); // recurrence
  memo.set(n, result);                   // remember it before returning
  return result;
}

// Bottom-up: the same recurrence, filled into a table from small to large.
function fibTable(n: number): number {
  if (n <= 1) return n;
  const dp: number[] = new Array(n + 1).fill(0); // one cell per subproblem, 0..n
  dp[0] = 0;                                     // base cases
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {                 // order: left to right
    dp[i] = dp[i - 1] + dp[i - 2];               // recurrence
  }
  return dp[n];                                  // answer cell
}

// 2D tables (two strings, grids): build each row separately.
function makeTable(rows: number, cols: number, fill: number): number[][] {
  // Array.from calls the function once per row, so every row is its own array
  return Array.from({ length: rows }, () => new Array(cols).fill(fill));
}

Worked example

1. Start with plain recursion, because it's the easiest to get right. To arrive at cell (r, c) the robot came either from above, (r - 1, c), or from the left, (r, c - 1). Any cell in the top row or left column has exactly one route: a straight line.

   function pathsSlow(r: number, c: number): number {
     if (r === 0 || c === 0) return 1;                  // straight line along the edge
     return pathsSlow(r - 1, c) + pathsSlow(r, c - 1);  // from above + from the left
   }
   // answer for a 3 × 4 grid: pathsSlow(2, 3)
   

2. Notice the repeats. pathsSlow(1, 1) is asked by both pathsSlow(2, 1) and pathsSlow(1, 2), and it gets much worse as the grid grows. The recursion reaches a base case once per route. An 18 × 18 grid has over 2.3 billion routes. These are overlapping subproblems, so it's time for DP.

3. Apply the recipe. State: dp[r][c] = number of routes from the start to cell (r, c). Recurrence: dp[r][c] = dp[r - 1][c] + dp[r][c - 1]. Base cases: every cell in row 0 and column 0 is 1. Order: row by row, left to right, so the cell above and the cell to the left are ready. Answer: dp[rows - 1][cols - 1].

4. Turn the recipe into code. Filling the whole table with 1 covers the base cases in one go.

   function gridPaths(rows: number, cols: number): number {
     const dp: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(1));
     for (let r = 1; r < rows; r++) {
       for (let c = 1; c < cols; c++) {
         dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above + from the left
       }
     }
     return dp[rows - 1][cols - 1];
   }
   

5. Check it on 3 × 4 by filling the table by hand. Each cell is the one above plus the one to its left, and the answer cell is 10. Edge cases: a 1 × 1 grid returns 1 (one route: stay put), and a 1 × n grid returns 1. Both work because the loops never run and the table is all 1s.

   // row 0:  1  1  1  1
   // row 1:  1  2  3  4
   // row 2:  1  3  6  10   <- answer
   

Common mistakes

• Coding before writing the state in words: if you can't finish the sentence “dp[i] means…”, the recurrence is guesswork and off-by-one errors follow.
• Wrong base case for counting problems: there's usually 1 way to do nothing, not 0. Setting the empty case to 0 makes every answer 0.
• Filling in the wrong order: reading dp[i + 1] while looping i upwards uses a cell that's still 0, so answers come out too small.
• Building a 2D table with new Array(rows).fill(new Array(cols).fill(0)): every row is the same array, so writing one cell changes that column in every row. Use Array.from with a function.
• Creating the memo cache inside the recursive function body: each call gets a fresh, empty cache, so nothing is reused. It's as slow as plain recursion. Create the cache once and pass it down.

Cost

In interviews