Dynamic programming basics

In plain English

Dynamic programming solves a big problem by breaking it into smaller subproblems whose answers are reused. Overlapping subproblems means the same smaller problem is solved many times, so caching its answer saves repeated work. Memoisation is a top-down technique that stores each answer in a lookup table as soon as it is computed, usually inside a recursive function. Tabulation is a bottom-up technique that fills a table in order from the smallest subproblem to the largest, usually with a loop. The Fibonacci sequence is the classic example: the naive recursion recomputes the same numbers over and over, while storing or filling them makes it fast.

Step by step

1. 1Write the naive recursive Fibonacci and notice it repeats work.
2. 2Add a cache object so each n is computed once.
3. 3Rewrite the same idea as a loop that fills a table from 0 upward.
4. 4Run both versions on n = 30 and compare how they feel.

function fib(n) {
  if (n <= 1) return n
  const table = [0, 1]
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2]
  }
  return table[n]
}

function fibMemo(n, cache = {}) {
  if (n <= 1) return n
  if (n in cache) return cache[n]
  cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache)
  return cache[n]
}

console.log(fib(10))
console.log(fibMemo(10))

Common mistakes

• Treating every recursive problem as dynamic programming is wrong, because DP only helps when subproblems overlap.
• Memoising a function that never repeats a subproblem just adds table overhead without saving any work.
• Filling the table in the wrong order in tabulation breaks the solution, because an entry may depend on a value that is not computed yet.
• Passing the cache by value or creating a new one on each call defeats the point of memoisation, because nothing is ever reused.