Dynamic Programming Explained

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

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

// fib(5) calls fib(3) twice, fib(2) three times, fib(1) five times.
// fib(50) makes about 2.5 billion calls, nearly all of them repeats.