Introduction to Dynamic Programming

Dynamic programming (DP) is a technique for solving optimization and counting problems by decomposing them into smaller subproblems, solving each subproblem once, and reusing those solutions. The result is often a dramatic drop from exponential to polynomial time.

Two Conditions for DP

A problem is a good candidate for DP when it exhibits both:

Optimal substructure — An optimal solution to the overall problem can be built from optimal solutions to its subproblems. For example, the shortest path from A to C through B requires the shortest path from A to B plus the shortest path from B to C.

Overlapping subproblems — The same subproblems are solved repeatedly during a naive recursive solution. This is different from divide-and-conquer (merge sort), where subproblems are independent and never repeated.

DP vs Greedy vs Divide-and-Conquer

Greedy algorithms make one locally optimal choice at each step without reconsidering past decisions. They are faster but only correct for problems with the greedy-choice property. DP always finds the global optimum by exhaustively considering all possibilities — with caching to avoid repeating work.

Fibonacci as a Motivator

Naive recursion for Fibonacci recomputes the same values over and over:

// Naive — exponential O(2^n)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// DP with a cache — linear O(n)
function fibDP(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibDP(n - 1, memo) + fibDP(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibDP(40)); // 102334155, instant

fib(40) makes over a billion recursive calls without caching. With a cache, each value from 2 to n is computed exactly once — O(n) time, O(n) space.

The DP Thought Process

Every DP solution follows the same four steps:

1. Define state — what information fully describes a subproblem?
2. Write the recurrence — how does the answer to state n depend on smaller states?
3. Identify base cases — what states have trivially known answers?
4. Determine evaluation order — ensure smaller states are solved before larger ones.

The next two lessons cover the two main implementation styles: top-down memoization and bottom-up tabulation.

Up Next

Learn how to implement top-down DP with a recursive function and a cache.