What is dynamic programming?

Dynamic programming (DP) is a way to solve problems that break into smaller problems of the same kind — like recursion — when those smaller problems repeat. Instead of solving the same one again and again, you solve each one once, store its answer, and look it up every time it's needed again. That single idea turns many exponential searches into fast, polynomial-time algorithms.

The call tree of a plain recursive fib(5) has 15 calls. fib(3) is computed twice and fib(2) three times; the orange nodes are repeated work. Dynamic programming computes each of fib(0) to fib(5) exactly once, left to right: 0, 1, 1, 2, 3, 5 — six steps instead of fifteen calls.

The two ingredients

A problem can be solved with DP when it has both of these:

Overlapping subproblems — a recursive solution asks the same smaller question many times. fib(5) needs fib(3) twice; a grid path count needs the count from the same cell over and over. (Merge sort splits into subproblems too, but they never repeat — that's plain divide and conquer, not DP.)
Optimal substructure — the answer to the big problem is built from the answers to smaller problems. The cheapest way up a staircase ends with the cheapest way to one of the two steps below; the longest common subsequence of two strings comes from the LCS of their shorter prefixes.

From recursion to DP: three steps

Almost every DP solution grows from a plain recursion, and you'll see these three versions in every lesson of this course:

1. Plain recursion — write the recurrence directly. Correct but exponential, because it re-solves the overlapping subproblems.
2. Memoization (top-down) — the same recursion, plus a cache: before computing a subproblem, check whether it's been solved. Next lesson.
3. Tabulation (bottom-up) — skip the recursion: fill a table from the smallest subproblems upward, in an order where everything a cell needs is already filled. Often followed by saving memory — keeping only the part of the table still needed.

Dry-run simulator

fib(n): the call tree

The plain recursion: watch how often the same small calls come back.

1function fib(n) {2  if (n <= 1) return n;                  // base cases: fib(0) = 0, fib(1) = 13  return fib(n - 1) + fib(n - 2);        // two calls: the call tree branches4}

JavaScript4 lines

Why it's so much faster

DP's running time is simple to count: the number of distinct subproblems × the work to solve one (given the answers to the smaller ones). Fibonacci has n + 1 subproblems, each one addition: O(n), instead of about 1.6ⁿ calls. The memory is the size of the table — unless you shrink it, which the fourth lesson shows.

problem                      subproblems        work each     time
Fibonacci                    n                  O(1)          O(n)
Climbing stairs              n                  O(1)          O(n)
Unique paths in a grid       m × n              O(1)          O(m · n)
Longest common subsequence   m × n              O(1)          O(m · n)
Coin change (amount A)       A                  O(coins)      O(A · coins)
Longest increasing subseq.   n                  O(n)          O(n²)

How to recognise a DP problem

It asks for a count (how many ways), an optimum (minimum cost, maximum profit, longest, shortest) or a yes/no (can it be done?) — not for a list of every solution (that's backtracking).
It's described as a sequence of decisions: take or skip, step one or two, match or edit a letter.
A brute-force recursion is easy to write but times out, because the same state comes up again and again.
The constraints are moderate: n up to a few thousand for O(n²), up to 10⁵ or 10⁶ for O(n).

Key takeaways

DP = recursion + remembering answers to repeated subproblems.
It needs overlapping subproblems and optimal substructure.
Time = number of states × work per state; memory = the table (often shrinkable).
Write the plain recursion first, then memoize it, then turn it into a table.

Was this helpful?