DP Cheatsheet

Complexity budget

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

Total	Feasible $n$
$O(n)$	$10^7$
$O(n\log n)$	$10^6$
$O(n\sqrt{n})$	$10^5$
$O(n^2)$	$5000$
$O(n^2\log n)$	$2000$
$O(n^3)$	$400$
$O(2^{n}n)$	$22$
$O(2^n{n}^2)$	$18$
$O(3^n)$	$16$
$O(n!)$	$11$

State shape by problem type

Problem smells like	State
a prefix decision	dp[i]
two sequences	dp[i][j]
a contiguous range	dp[l][r]
items with a budget	dp[i][w]
a subtree	dp[v], often dp[v][0/1]
a subset ($n\le 22$)	dp[mask]
digits of a number	dp[pos][tight][started][...]
a grid filled cell by cell	dp[row][profile]
a position with a last choice	dp[i][last]
an amount of a resource used	dp[i][used]

Optimisation lookup

Transition	Requirement	Technique	Result
${\min }_{j}dp[j]$ over a fixed window	none	monotone queue	$O(n)$
${\min }_{j}dp[j]$ over an arbitrary range	none	segment tree	$O(n\log n)$
${\min }_j(dp[j]+m_j{x}_i)$	linear in $x$	CHT / Li Chao	$O(n)$ / $O(n\log n)$
${\min }_k(dp[i-1][k]+C(k,j))$	monotone argmin	D&C DP	$O(kn\log n)$
${\min }_k(dp[l][k]+dp[k][r]+C)$	quadrangle inequality	Knuth	$O(n^2)$
”exactly $k$ groups”, $k$ huge	convex in $k$	Aliens trick	$O(n\log C)$
value is a convex function	convexity	slope trick	$O(n\log n)$
linear, constant transition, huge $n$	linearity	matrix power	$O(k^3\log n)$
boolean feasibility	—	bitset	$/64$
sum over all submasks	—	SOS DP	$O(2^{n}n)$
row minima, totally monotone	Monge	SMAWK	$O(n)$

Loop-direction rules

DP	Direction
0/1 knapsack, 1D array	weight decreasing
Unbounded knapsack, 1D array	weight increasing
Interval DP	by increasing length
dp[l][r] from dp[l+1][r]	$l$ decreasing
Tree DP	post-order (or reverse BFS order)
Bitmask DP	mask increasing
Coin change combinations	coin loop outside
Coin change permutations	amount loop outside

Debugging checklist

1. Is the state complete? Does anything outside the state affect the future?
2. Is the state minimal? Is any dimension never actually used?
3. Base cases: are unreachable states initialised to $\pm \infty$ rather than 0?
4. Loop order: does every dependency precede its use?
5. Overflow: is long long needed? Are you taking % MOD after every addition and multiplication?
6. Off by one: is dp[i] “first $i$ elements” or “up to index $i$”? Pick one and stay consistent.
7. Multiple test cases: is everything reset?
8. Recursion depth: could the memoised version overflow the stack?
9. Answer extraction: is it dp[n], or the max over the last row?

Sanity checks before submitting

• Run the DP against a brute force on random small inputs. This catches almost everything.
• Test $n=1$, $n=0$, all-equal values, and the maximum constraint.
• If the answer should be non-negative and your $-\infty$ sentinel is $-10^{18}$, check that adding to it never underflows.

When DP is the wrong tool

Symptom	Try instead
States depend on each other cyclically	Dijkstra / Bellman-Ford
An exchange argument works	greedy
”Minimise the maximum”	binary search the answer
Matching or assignment structure	matching / flow
The state is a set with no small summary	meet in the middle
Counting with independent parts	combinatorics / generating functions

See also: Dynamic Programming · Designing States · Complexity Cheatsheet