Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Dynamic Programming

Dynamic Programming Explained

Written by Updated

Dynamic programming has an intimidating name for a simple idea: work something out once, write it down, and look it up next time instead of working it out again.

The two conditions

A problem is a DP problem when both of these hold:

  • Overlapping subproblems - the same smaller question comes up repeatedly.
  • Optimal substructure - the best answer is built from the best answers to the smaller questions.

Miss the first and there is nothing to cache. Miss the second and combining smaller answers gives the wrong result.

Seeing the repetition

The same work, over and over

javascript

function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

// Count how many times each value is recomputed.
const calls = new Map()

function counted(n) {
  calls.set(n, (calls.get(n) || 0) + 1)
  if (n <= 1) return n
  return counted(n - 1) + counted(n - 2)
}

console.log(fib(5))              // 5
counted(5)
console.log("fib(3) computed", calls.get(3), "times")  // 2
console.log("fib(2) computed", calls.get(2), "times")  // 3
console.log("fib(1) computed", calls.get(1), "times")  // 5

// The call count follows 2 x fib(n + 1) - 1, so fib(50) costs about
// 40 billion calls — nearly all of them recomputing the same values.

Memoisation - top down

Keep the recursion, add a cache. Usually the easier of the two to write.

Memoised

javascript

function fib(n, cache = new Map()) {
  if (n <= 1) return n
  if (cache.has(n)) return cache.get(n)

  const result = fib(n - 1, cache) + fib(n - 2, cache)
  cache.set(n, result)
  return result
}

console.log(fib(50))   // instant

Same code, one cache. Exponential becomes linear because each value is computed once.

Tabulation - bottom up

Drop the recursion. Fill a table from the smallest case upward.

Tabulated, then optimised

javascript

function fib(n) {
  if (n <= 1) return n

  const table = new Array(n + 1)
  table[0] = 0
  table[1] = 1

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2]
  }

  return table[n]
}

// Only the last two entries are ever read, so the table is unnecessary.
function fibSmall(n) {
  let previous = 0
  let current = 1

  for (let i = 2; i <= n; i++) {
    ;[previous, current] = [current, previous + current]
  }

  return n <= 1 ? n : current
}

console.log(fib(30))       // 832040
console.log(fibSmall(30))  // 832040, using two variables

That last step - noticing you only need the last two values - is the standard DP space optimisation. It turns O(n) memory into O(1).

Choosing between them

  • Memoisation - closer to how you thought about the problem, computes only what is needed, risks stack overflow when deep.
  • Tabulation - no recursion, no stack limit, allows the space trick, but computes every entry whether or not you need it.

Write the recursion first. Add a cache. Convert to a table only if depth becomes a problem or you want the space optimisation.

The two conditions

DP applies when a problem has overlapping subproblems - the same smaller question is asked repeatedly - and optimal substructure, meaning the best answer is built from best answers to those smaller questions. Both must hold. Without overlap you have plain divide and conquer; without optimal substructure, caching is simply wrong.

Top-down versus bottom-up

The same problem, both ways

javascript

// Top-down: recursion plus a cache. Easiest to derive.
function climbMemo(n, memo = new Map()) {
  if (n <= 2) return n
  if (memo.has(n)) return memo.get(n)

  const result = climbMemo(n - 1, memo) + climbMemo(n - 2, memo)
  memo.set(n, result)
  return result
}

// Bottom-up: a table, no recursion, no stack limit.
function climbTable(n) {
  if (n <= 2) return n
  const table = new Array(n + 1)
  table[1] = 1
  table[2] = 2
  for (let i = 3; i <= n; i++) table[i] = table[i - 1] + table[i - 2]
  return table[n]
}

// Bottom-up with O(1) space: only the last two values matter.
function climbRolling(n) {
  if (n <= 2) return n
  let prev = 1
  let curr = 2
  for (let i = 3; i <= n; i++) [prev, curr] = [curr, prev + curr]
  return curr
}

console.log(climbMemo(10))    // 89
console.log(climbTable(10))   // 89
console.log(climbRolling(10)) // 89

Derive it top-down, because the recursion mirrors how you reasoned about the problem. Convert to bottom-up when recursion depth is a risk, then drop to rolling variables once you can see how far back the recurrence actually reaches.

  • Write the recurrence in words before writing any code.
  • Identify the state - what arguments fully describe a subproblem.
  • Nail the base cases; most DP bugs live there.
  • Only then decide between a Map, a 1D table, or two variables.
PreviousUnion-Find (Disjoint Sets)NextClassic DP Problems