Dynamic Programming

Solve a problem once for each smaller version of it, store each answer, and build the full answer from the stored ones.

Overview

What dynamic programming is

Dynamic programming (DP) is a way to solve a problem by solving smaller versions of it first. Each smaller version is a subproblem. You solve each subproblem once, store its answer, and reuse the stored answer every time it comes up again. Richard Bellman introduced the method and its name in the 1950s.

DP fits when a problem has two properties.

Overlapping subproblems. A plain recursive solution asks the same question many times.
Optimal substructure. The best answer to the whole problem is built from the best answers to its subproblems.

The Fibonacci numbers show the first property. To get fib(4), plain recursion computes fib(2) twice and fib(1) three times. The tree grows exponentially with n.

The number of calls explodes. With a stored answer per value, fib(n) needs only n + 1 distinct computations.

10 — 177 — 11
20 — 21,891 — 21
30 — 2,692,537 — 31

Top-down and bottom-up

There are two ways to write the same DP. Both do the same amount of work in the worst case.

Top-down (memoization). Write the natural recursion, then add a cache. Before computing a state, check the cache. After computing it, store it.
Bottom-up (tabulation). Fill a table in a loop, starting from the base cases, so that every value a cell needs is already there.

Written as — Recursion plus a cache — Loops over a table
States computed — Only the ones reached — All of them
Main risk — Deep recursion can hit the stack limit — You must pick the fill order
Space tricks — Hard — Easy: keep only the rows you still need
Best first step — Yes, it follows the recurrence — Convert to it once the recurrence is right

In Python, functools.cache (Python 3.9 and later) turns a recursive function into a memoized one, as long as its arguments are hashable. Python also caps recursion depth to protect the C stack, so a top-down solution on a large input can raise RecursionError. That is a common reason to switch to bottom-up.

The five-step recipe

Every DP solution answers the same five questions. Say each answer out loud before you code.

Take House Robber: houses in a row hold some money, and you cannot rob two neighbors. What is the most you can take?

State. dp[i] is the most money from houses 0 to i.
Recurrence. At house i, either skip it (dp[i-1]) or take it and skip its neighbor (dp[i-2] + value). dp[i] is the larger of the two.
Base cases. Before the first house the total is 0.
Order. Left to right.
Answer. The last cell.

Here is a trace on the houses [2, 7, 9, 3, 1]. Each row fills one cell.

0 — 2 — 0 — 0 + 2 = 2 — 2
1 — 7 — 2 — 0 + 7 = 7 — 7
2 — 9 — 7 — 2 + 9 = 11 — 11
3 — 3 — 11 — 7 + 3 = 10 — 11
4 — 1 — 11 — 11 + 1 = 12 — 12

The answer is 12 (houses 0, 2 and 4). Each cell reads only the two cells before it, so two variables are enough and the space drops from O(n) to O(1).

Two dimensions: the LCS table

Some problems need two indexes in the state. The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both, in order but not necessarily side by side. Let dp[i][j] be the LCS length of the first i characters of one string and the first j of the other.

If the two last characters match, dp[i][j] = dp[i-1][j-1] + 1.
Otherwise, drop one of them and keep the better result: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

The full table for 'abcde' against 'ace'. Row 0 and column 0 are the empty prefix.

'' — 0 — 0 — 0 — 0
a — 0 — 1 — 1 — 1
b — 0 — 1 — 1 — 1
c — 0 — 1 — 2 — 2
d — 0 — 1 — 2 — 2
e — 0 — 1 — 2 — 3

The bold cells are the matches along the way, and the bottom-right cell is the answer: 3 ('ace'). The table has (m + 1) × (n + 1) cells and each takes O(1), so the time is O(mn). Each row reads only the row above it, so two rows are enough for the length. The Unix diff tool is built on this same problem: it finds the lines two files have in common and reports the rest as changes.

Knapsack: the loop direction matters

In the 0/1 knapsack, each item has a weight and a value, and you can take each item at most once. dp[c] is the best value with capacity c. For each item, dp[c] = max(dp[c], dp[c - weight] + value).

With a one-row table, the direction of the capacity loop decides the problem you solve.

Loop capacity downward: dp[c - weight] still holds the value from before this item, so each item is used at most once. That is 0/1 knapsack.
Loop capacity upward: dp[c - weight] may already include this item, so an item can be reused. That is the unbounded knapsack (Coin Change works this way).

Here is the row after each item, for weights [1, 3, 4], values [15, 20, 30] and capacity 4.

Start — 0 — 0 — 0 — 0 — 0
Weight 1, value 15 — 0 — 15 — 15 — 15 — 15
Weight 3, value 20 — 0 — 15 — 15 — 20 — 35
Weight 4, value 30 — 0 — 15 — 15 — 20 — 35

The answer is 35 (the items of weight 1 and 3). Running the same loop upward gives 60, because it takes the weight-1 item four times. That is right for the unbounded version and wrong here.

The common families

Most DP problems belong to a handful of families. Recognizing the family tells you the state.

Linear (1D) — dp[i]: best up to i — from dp[i-1], dp[i-2] — House Robber — O(n)
Two sequences — dp[i][j]: prefixes i and j — match, or drop one side — LCS, Edit Distance — O(mn)
Grid — dp[r][c]: best path to a cell — from top and left — Unique Paths — O(rows × cols)
Knapsack — dp[c]: best with capacity c — take or skip each item — Coin Change — O(n × capacity)
Subsequence (LIS) — dp[i]: best ending at i — over all j before i — Longest Increasing Subsequence — O(n²), or O(n log n)
Interval — dp[i][j]: best for range i..j — over all split points k — Burst Balloons — O(n³)
State machine — dp[i][s]: best on day i in state s — move between states — Stock with Cooldown — O(n × states)
Bitmask — dp[mask]: best for a subset — add one element — Traveling Salesman — O(2ⁿ × n) or more

The running time of any DP is the number of states times the work per state. LIS has n states and each looks back over up to n earlier elements, so O(n²).

Is it DP, greedy or backtracking?

What you will be able to do

Spot a DP problem from its question: best value, number of ways, or can it be done.
Define the state, the recurrence, the base cases and the fill order before writing code.
Write the same solution top-down and bottom-up, and say when to prefer each.
Trace a small table by hand to check the recurrence.
Cut the space by keeping only the rows or cells the recurrence reads.

When to use it

The question asks for a minimum or maximum (fewest coins, most profit)
The question asks how many ways something can be done
The question asks whether a target can be reached (can the string be split, can the sum be made)
A brute-force recursion would solve the same subproblem many times
The input is a sequence, a pair of strings, a grid or a capacity
Each decision (take or skip, match or drop) leads to a smaller version of the same problem

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio