i. DP Foundations

A DP is a shortest/longest path or a sum over paths in an acyclic state graph. Designing one means picking states (what about the past affects the future), transitions (edges), and an order (a topological order of the states). Time = states × transition cost, and every optimisation in this chapter attacks one of those two factors.

Proof: why a DP is correct

Number the states in a topological order of the dependency graph. By strong induction along that order: if every state a state depends on already holds its true value, the transition (which is the recurrence derived from the problem by considering the last decision) produces the true value for this state. The base cases have no dependencies. Optimal substructure is exactly the statement that the recurrence is correct: an optimal solution for a state, minus its last decision, is an optimal (or at least an equally good) solution for the predecessor state. If the state graph has a cycle, there is no such order, and you need a shortest-path algorithm (Dijkstra, Bellman-Ford) or a fixed-point / linear-system argument instead.

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 to $v$ needs, so smaller subproblems don’t combine into the bigger one. (On a DAG it works, since there’s no choice of which vertices to “save” for later.)
• Too many states with no compression. If the state genuinely needs the full set of visited vertices and $n=50$, no reduction trick shrinks $2^{50}$ — look for a different model, not a bigger machine.
• Greedy already settles it. Don’t build a DP for a problem an exchange argument proves optimal for — see Exchange Arguments; a DP that happens to also get the right answer is strictly more code and more bug surface for no gain.
• Only overlapping subproblems, no optimal substructure: that’s memoised search (e.g. counting paths in a DAG with cycles removed by state, game-tree search) — correct, but “optimal substructure” isn’t the reason it works, so don’t cite it as justification.

Designing the state

The state must hold everything about the past that affects the future, and nothing more.

• Ask: “to finish the job, what would someone need to be told?”
• Sort first so a dimension becomes implicit (intervals by end, items by deadline, edges by weight).
• Swap value and dimension: replace dp[i][x] = feasible? with dp[i] = best x when feasibility is monotone in $x$ (LIS tails, “minimum weight for value $v$” knapsack when values are small).
• Keep only a summary: “was the last element chosen”, “last value modulo $k$”, “how many open groups”, “the multiset of open things up to symmetry”.
• Count objects up to relabeling: “set of used items” becomes “number of used items” when the items are interchangeable.
• Contribution instead of configuration: if the cost is a sum over pairs/edges, decide each contribution at the moment it’s determined (e.g. “open brackets” style DPs: track how many segments are still open and pay for all of them per step).
• Defer decisions (“exchange the order of summation”): decide only what is needed now, keep a count of pending choices, and resolve them later (connected-component DP, insertion DP).
• Fix the extremal element: iterate over the position or value of the maximum/minimum and split the problem around it (Cartesian-tree DP, interval DP over the last removed element).

Problem smells like	State
prefix decisions	dp[i], dp[i][last], dp[i][used]
two sequences	dp[i][j]
contiguous range, merge/remove operations	dp[l][r] (sometimes dp[l][r][extra])
budget	dp[i][w] or dp[i][value] = min weight
subtree	dp[v][...]
subset, $n\le 20$	dp[mask], dp[mask][last]
digits	dp[pos][tight][started][...]
grid, narrow width	dp[cell][profile]
process over time with a few counters	dp[t][counters]
two sequences, no-two-adjacent-chosen	dp[i][j][0/1] (first $i$ elements, $j$ chosen, last taken or not) — the move from “the set of chosen elements” to “was the previous one chosen” is the archetypal state reduction: a problem with naive state dp[i][k][\text{mask of chosen}] collapses to $O(nk)$ states, $O(1)$ transition, once you notice only the previous choice, not the whole chosen set, affects feasibility of the next one

Named examples by shape: dp[i] — LIS, house robber, coin change, word break; dp[i][j] — LCS, edit distance, string alignment; dp[l][r] — matrix chain, burst balloons, palindrome partitioning; dp[v][0/1] — independent set on a tree, tree colouring; dp[mask][i] — Held–Karp (TSP); dp[row][profile] — broken-profile DP.

Feasibility by state count

Total work	Feasible $n$ (1-2 s)
$O(n)$, $O(n\log n)$	$10^6$–$10^7$
$O(n\sqrt{n})$	$2\cdot 10^5$
$O(n^2)$	$5000$–$10^4$
$O(n^2\log n)$	$2000$–$3000$
$O(n^3)$	$400$–$500$
$O(2^{n}n)$	$20$–$22$
$O(2^n{n}^2)$	$17$–$18$
$O(3^n)$	$14$–$16$

Memoisation vs tabulation

	Top-down (memo)	Bottom-up (table)
order	implicit	must be derived
visits	only reachable states	all states
speed	function calls (2–5× slower)	tight loops, vectorisable
memory tricks	hard	rolling arrays, bitsets
depth	stack overflow risk at $10^5$–$10^6$	none
best for	sparse or weird states (hash of a board, tree hashes)	regular grids of states

Use a separate vis array (or version stamps for many test cases: if (stamp[s] == tc) return memo[s]) rather than a sentinel value that might be a real answer.

Non-numeric states: anything hashable works as a memo key — strings, tuples, canonical board positions, tree hashes. This is where top-down genuinely beats bottom-up: there is often no sensible way to enumerate such states in a fixed order, but there is always a way to recurse into them. Game solving, puzzle search, and “count distinct configurations up to symmetry” problems live here.

Bug	Symptom
Caching before the base-case check	wrong answers on trivial inputs
A parameter that affects the answer but isn’t in the key	wrong answers, not reproducible
A parameter in the key that doesn’t affect the answer	correct but far too slow
Forgetting to reset between test cases	first test right, rest wrong
Sentinel value collides with a real answer	silent recomputation or wrong answer
Recursion on a cyclic state graph	infinite loop — needs Dijkstra/Bellman-Ford, not memoization

Memoization silently assumes the state graph is acyclic (the proof at the top of this note requires a topological order to exist). If a state can depend on itself, directly or through a chain, memoization loops forever or returns garbage.

Order and direction

Recurrence	Loop order
dp[i] from smaller i	$i$ increasing
dp[l][r] from strictly shorter intervals	by length, or $l$ decreasing then $r$ increasing
tree	post-order (reverse BFS order works)
dp[mask] from submasks	mask increasing
0/1 knapsack in one array	capacity decreasing
unbounded knapsack in one array	capacity increasing
combinations (order irrelevant)	items outer, amount inner
sequences (order matters)	amount outer, items inner

Proof: the loop direction in one-array knapsack

In 0/1 knapsack, dp[w] after processing item $i$ must equal $\max (\text{old }dp[w],\text{old }dp[w-c]+v)$. Iterating $w$ downward, when we update dp[w] the cell dp[w - c] (smaller index) hasn’t been touched in this pass yet, so it still holds the old value: the item is used at most once. Iterating upward, dp[w - c] has already been updated in this pass and may already include item $i$, so the item can be used repeatedly, which is exactly the unbounded recurrence $dp[w]=\max (dp[w],dp[w-c]+v)$ over the new row. The combinations/sequences rule is the same idea: with items in the outer loop each multiset is built in one canonical item order, while with the amount outer loop every ordering is a different path.

Push vs pull: pull (dp[i] = f(dp[j], j < i)) mirrors the recurrence; push (dp[j] += ... from dp[i]) is easier when successors are simple (grid moves, “add one item”). Both visit the same edges.

Cache locality for large tables: for a 2D table, iterate the last index in the inner loop so memory access is sequential. Swapping the loop order on a $5000\times 5000$ table can cost a 5-10x slowdown from cache misses alone — enough to turn an accepted solution into a TLE, with no change to the asymptotic complexity.

Space and reconstruction

• Rolling rows: keep the last $k$ layers if the recurrence looks back $k$ layers.
• Bitsets for boolean DPs: $64\times$ less time and memory (Bitset).
• Reconstruction without a choice table: walk back from the answer and re-check which transition attains the stored value.
• Reconstruction in linear memory: Hirschberg-style divide and conquer, i.e. compute the forward DP to the middle layer and the backward DP from the end, find where the optimal path crosses the middle, recurse on both halves; $O(nm)$ time, $O(n+m)$ memory (Sequence DP).
• Checkpointing: store every $\sqrt{n}$-th layer, recompute blocks during traceback: $O(\sqrt{n}\cdot m)$ memory, 2× time.

Type	Elements in 256 MB
char / bool	$2.6\cdot 10^8$
short	$1.3\cdot 10^8$
int / float	$6.7\cdot 10^7$
long long / double	$3.3\cdot 10^7$
bits (bitset)	$2.1\cdot 10^9$

A long long table of $5000\times 5000$ is 200 MB — too big for most limits. The same table as int is 100 MB — borderline. Rolled to two rows, it’s 40 KB.

vector<bool> is not an array of bool

It’s a bit-packed specialisation: 8x smaller but slower per access, and it can’t give you a pointer to an element. For a DP table it’s usually the right memory trade-off; for hot inner loops prefer bitset (faster, fixed size) or vector<char>.

Optimisation map

Transition shape	Condition	Technique	Cost
${\min }_{j\in \text{window}}d{p}_j$	sliding window	monotone deque (Monotone)	$O(n)$
${\min }_{j\in [l_i,r_i]}d{p}_j+g(i)$	any ranges	segment tree / sparse table on $dp$	$O(n\log n)$
${\min }_{j}d{p}_j+a_j{b}_i$	linear in a parameter	CHT / Li Chao (CHT)	$O(n)$–$O(n\log n)$
${\min }_{k}d{p}_k^{\prime }+C(k,j)$ over layers	monotone argmin / Monge	D&C opt (D&C)	$O(kn\log n)$
${\min }_{k}d{p}_{l,k}+d{p}_{k,r}+C(l,r)$	quadrangle inequality	Knuth (Knuth)	$O(n^2)$
${\min }_{j}d{p}_j+w(j,i)$, $w$ Monge	1D1D	binary-search queue, SMAWK, LARSCH	$O(n\log n)$ / $O(n)$
exactly $k$ parts, answer convex in $k$	concavity	Aliens / WQS (Aliens)	$\times O(\log C)$
$dp$ is convex piecewise linear in a value	convexity	slope trick (Slope Trick)	$O(n\log n)$
linear recurrence, constant transitions, huge $n$	linearity	matrix power / Berlekamp–Massey (Matrix DP)	$O(k^3\log n)$ / $O(k\log k\log n)$
point updates to the input, re-answer	DP is a monoid product	dynamic DP (Dynamic DP)	$O(k^3\log n)$ per update
sum over submasks	—	SOS / subset convolution (SOS)	$O(2^{n}n)$ / $O(2^n{n}^2)$
polynomial-like counting DP	generating functions	power series (Power Series)	$O(n\log n)$
knapsack with small item costs	bounded weights	weight-capped arguments, (max,+) concave convolution (Knapsack)	varies

Checklist

1. Complete state? Is anything outside the state influencing the future?
2. Minimal state? Is any dimension determined by the others?
3. Unreachable states at $\pm \infty$ (not 0); $-\infty +x$ never underflows.
4. Every dependency computed before use.
5. Answer: dp[n] or the best over the last layer?
6. Multiple test cases: reset only what was touched.
7. Before submitting, compare with a brute force on random small inputs (Stress Testing).