Introduction to Dynamic Programming

Dynamic programming applies when a problem has two properties:

1. Optimal substructure — an optimal solution is built from optimal solutions to subproblems.
2. Overlapping subproblems — the same subproblem is reached many times, so caching pays.

If only the first holds, you have divide and conquer. If only the second, you have memoised search with no guarantee of optimality.

The four questions

Answer these, in order, and the code writes itself.

1. State. What is the minimum information needed to describe a subproblem? Everything you need to remember and nothing more.
2. Transition. How does a state’s answer follow from smaller states?
3. Base case. Which states are answered directly?
4. Order. In what order can states be computed so that every dependency is ready? (This is a topological order of the state graph.)

Worked example: climbing stairs

You can climb 1 or 2 steps at a time. How many ways to reach step $n$?

1. State: dp[i] = number of ways to reach step $i$.
2. Transition: dp[i] = dp[i-1] + dp[i-2] — the last move was 1 or 2 steps.
3. Base: dp[0] = 1, dp[1] = 1.
4. Order: increasing $i$.

vector<long long> dp(n + 1);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

Only two previous values are needed, so this reduces to $O(1)$ space — see Space Optimization.

Complexity

$\text{time}=(\#\text{states})\times (\text{cost per transition}).$

This is the single most useful formula in DP. Before writing any code, count the states and the transition cost and check the product against the limit.

States	Transition	Total	Typical bound
$O(n)$	$O(1)$	$O(n)$	$n\le 10^7$
$O(n)$	$O(n)$	$O(n^2)$	$n\le 5000$
$O(n^2)$	$O(1)$	$O(n^2)$	$n\le 5000$
$O(n^2)$	$O(n)$	$O(n^3)$	$n\le 400$
$O(2^n)$	$O(n)$	$O(2^{n}n)$	$n\le 22$
$O(n\cdot W)$	$O(1)$	$O(nW)$	$nW\le 10^8$

Top-down vs bottom-up

	Memoization (top-down)	Tabulation (bottom-up)
Written as	recursion + cache	loops
Order	implicit	explicit — you must get it right
Visits	only reachable states	all states
Overhead	function calls, stack depth	none
Space optimisation	hard	easy (rolling arrays)
Best for	irregular state spaces, unclear order	tight loops, memory-constrained

Write the memoised version first to get the recurrence right, then convert to tabulation if you need the speed or the space saving.

When DP does not apply

• No optimal substructure. Longest simple path in a general graph — an optimal path to $v$ may use vertices a longer path needs. (On a DAG it works.)
• Too many states. If the state needs the full set of visited vertices and $n=50$, no amount of cleverness compresses $2^{50}$.
• Greedy is enough. Do not build a DP for a problem an exchange argument settles — see Exchange Arguments.

How to find the state

The recurring difficulty. Some prompts:

• What did the previous decision change about my situation?
• If I told a friend the current situation over the phone, what would I have to say?
• Can I reorder the input (sort it) so that the state gets smaller?
• Is a quantity monotone, so it can be dropped or binary-searched instead of stored?
• Can an expensive dimension be replaced by “the best value so far” (a running max/min)?

See also: Designing States · DP Cheatsheet · Algorithmic Paradigms