iii. Classic DP Problems

The classic problems are worth knowing less for themselves than for the patterns they introduce: linear recurrences, state machines, prefix DP with a validity predicate, inverting the DP (answer becomes an index), sorting to fix an order, and inclusion-exclusion over special cells.

Linear recurrences and tilings

Count	Recurrence / value
steps of size $\mathrm{1..}k$ (ordered)	$f_n=f_{n-1}+\cdots +f_{n-k}$ (sliding window sum)
steps from a set $S$	$f_n={\sum }_{s\in S}{f}_{n-s}$
$2\times n$ domino tilings	$F_{n+1}$
$3\times n$ domino tilings	$f_n=4f_{n-2}-f_{n-4}$ ($f_0=1,f_2=3$, odd $n$: 0)
$2\times n$ with dominoes and L-trominoes	$f_n=2f_{n-1}+f_{n-3}$
binary strings without two adjacent 1s	$F_{n+2}$
compositions of $n$ into parts $\ge 2$	$F_{n-1}$
$m\times n$ domino tilings (general)	profile DP (Profile DP) or Kasteleyn’s formula ${\prod }_{j\le \lceil m/2\rceil }{\prod }_{k\le \lceil n/2\rceil }\left(4{\cos }^2\frac{\pi j}{m+1}+4{\cos }^2\frac{\pi k}{n+1}\right)$

For huge $n$: matrix power or Kitamasa / Bostan–Mori (Linear Recurrences). Plain Fibonacci has a direct $O(\log n)$ via fast doubling, no matrix needed: $F_{2k}=F_k(2F_{k+1}-F_k)$, $F_{2k+1}=F_k^2+F_{k+1}^2$. If no recurrence is obvious, brute-force 20–50 terms, run Berlekamp–Massey, and check OEIS.

Variant	Change to the recurrence
cost instead of count	$\min$ (or $\max$) in place of $+$ — shortest path on a line
cannot repeat the same step twice in a row	add a “last step used” dimension
some step sizes are temporarily unusable	skip those terms for the affected $n$

Kasteleyn’s formula above is a special case of a general fact: counting perfect matchings of a planar graph is a Pfaffian (hence a determinant), computable in polynomial time — the FKT algorithm. Counting perfect matchings of a general graph is p-hard; planarity is exactly what makes the tiling count tractable in closed form.

Proof: the $3\times n$ and tromino recurrences

$3\times n$: let $f_n$ count full tilings and $g_n$ count tilings of a $3\times n$ board with one corner cell of the first column already covered. Looking at how the first column is covered: $f_n=2g_{n-1}+f_{n-2}$ (the left column is covered by one vertical domino plus a horizontal one, in two mirror ways, or by three horizontal dominoes), and $g_n=f_{n-1}+g_{n-2}$. Eliminating $g$ gives $f_n=4f_{n-2}-f_{n-4}$.
Dominoes and L-trominoes on $2\times n$: classify by the leftmost tile(s): a vertical domino ($f_{n-1}$), two horizontal dominoes ($f_{n-2}$), or an L-tromino starting a “zigzag” chain that ends with another tromino after $k\ge 0$ horizontal dominoes (2 orientations each). This gives $f_n=f_{n-1}+f_{n-2}+2{\sum }_{j\ge 3}{f}_{n-j}$; subtracting the same identity for $f_{n-1}$ gives $f_n=2f_{n-1}+f_{n-3}$.

State-machine DP: stock trading

States “holding / not holding” × “transactions used”; every extra rule is either a new state or an edge cost, and once the machine is drawn the code is mechanical:

Rule	Change
cooldown of 1 day after selling	add a cooldown state
transaction fee $f$	subtract $f$ on each sell
must hold $\ge d$ days before selling	index by days held so far
short selling allowed	add a symmetric short state

ll maxProfit(const vector<ll>& p, int k) {                 // at most k buy-sell pairs
    int n = sz(p);
    if (2 * k >= n) { ll s = 0; for (int i = 1; i < n; i++) s += max(0LL, p[i] - p[i - 1]); return s; }
    vector<ll> buy(k + 1, LLONG_MIN / 2), sell(k + 1, 0);
    for (ll x : p) for (int j = 1; j <= k; j++) buy[j] = max(buy[j], sell[j - 1] - x), sell[j] = max(sell[j], buy[j] + x);
    return sell[k];
}

• Unlimited transactions: sum of positive day-to-day differences.
• Huge $k$: profit is concave in $k$, so use the Aliens trick (Aliens Trick), or the greedy with a heap of local valleys/peaks merging cheapest pairs in $O(n\log n)$.
• “Buy at most one unit per day, sell any time, maximise profit” (CF 865D): push each price into a min-heap; if the current price beats the top, take the profit and push the price twice (one copy for “undo this sale later”). This is a regret greedy (Greedy).

Proof: unlimited transactions and the $2k\ge n$ shortcut

Any transaction buying on day $a$ and selling on day $b$ earns $p_b-p_a={\sum }_{i=a+1}^b(p_i-p_{i-1})$, and non-overlapping transactions use disjoint sets of differences. So any strategy earns at most ${\sum }_i\max (0,p_i-p_{i-1})$, and taking one transaction per maximal increasing run achieves it. The number of increasing runs is at most $\lceil n/2\rceil$, so with $k\ge n/2$ the limit never binds.

Prefix DP with a validity predicate

dp[i] from all dp[j] with s[j..i) valid: word break, palindrome partitioning, decoding digit strings, text justification. The cost is in testing validity:

• dictionary words: walk a trie from every reachable $j$, or run Aho–Corasick and follow dictionary suffix links (Aho–Corasick);
• palindromes: precompute pal[j][i] in $O(n^2)$, or use the eertree’s series links for $O(n\log n)$ min-cut palindrome partition (Eertree);
• convex segment costs (line breaking): Monge, so 1D1D optimisation applies (Monotone Optimizations).

int minPalCuts(const string& s) {                           // fewest palindromes
    int n = sz(s); vector<vector<char>> pal(n, vector<char>(n)); vector<int> dp(n + 1, INT_MAX); dp[0] = 0;
    for (int i = n - 1; i >= 0; i--) for (int j = i; j < n; j++) pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
    for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) if (pal[j][i - 1]) dp[i] = min(dp[i], dp[j] + 1);
    return dp[n];
}

Counting segmentations can be exponential, so always count modulo something; enumerate only when the output is bounded.

Enumerating all segmentations

The number of segmentations can be exponential ("aaaa...a" with dictionary {a, aa}). A memoised DFS that returns a list of strings blows up on such inputs even though the DFS itself is memoized — the blow-up is in the output size, not the recursion. Count with a DP instead, and only enumerate when the problem bounds the output.

Other prefix-DP-over-a-string shapes: decode ways ($d{p}_i$ from $d{p}_{i-1}$ and $d{p}_{i-2}$, digits to letters), concatenated words (word break with a length constraint), each dictionary word usable at most once (NP-hard in general — this breaks the simple prefix recurrence), allow at most $k$ unknown/wildcard characters (add a dimension for the count used).

Inverting the DP: egg dropping

$k$ eggs, $n$ floors, minimise worst-case drops. Instead of best[k][n], compute $f(e,t)$ = the most floors distinguishable with $e$ eggs and $t$ drops:

$f(e,t)=f(e-1,t-1)+f(e,t-1)+1,f(e,t)={\sum }_{i=1}^e\left(\genfrac{}{}{0ex}{}{t}{i}\right).$

int eggDrop(int k, ll n) {
    vector<ll> f(k + 1, 0); int t = 0;
    while (f[k] < n) { t++; for (int e = k; e >= 1; e--) f[e] = min(n, f[e] + f[e - 1] + 1); }
    return t;
}

With 1 egg the answer is $n$ (a linear scan from the bottom — no eggs to spare for binary search). With 2 eggs the answer is the least $t$ with $t(t+1)/2\ge n$ (14 for 100 floors); with $\ge {\log }_{2}n$ eggs it is binary search. The 2-egg optimum is achieved by decreasing gaps: for $n=100$, drop first at floor 14, then (if it survives) 27, then 39, … — never floor 50, because each break costs both an egg and a drop, so the next interval must shrink by one. The same inversion turns knapsack by capacity into knapsack by value, and “minimum operations to reach $X$” into “maximum reach with $t$ operations”.

Variants needing a different DP, not just a bigger table: minimising the expected number of drops (a DP over probability distributions, not the worst case); eggs with different individual fragility thresholds; counting the number of distinct strategies using exactly $t$ drops and $e$ eggs (the binomial sum above, read as a count rather than a bound).

Proof: recurrence and closed form

With $e$ eggs and $t$ drops, drop from some floor. If the egg breaks we must solve the floors below with $e-1$ eggs and $t-1$ drops, so at most $f(e-1,t-1)$ floors can be below; if it survives, at most $f(e,t-1)$ floors above; plus the floor tested. Placing the first drop at exactly floor $f(e-1,t-1)+1$ achieves the bound, so the recurrence is exact. For the closed form, a strategy is a binary decision tree of depth $t$; the threshold is determined by the leaf reached, and leaves correspond to break/survive strings of length $\le t$ with at most $e$ breaks. Formally, $g(e,t)={\sum }_{i=1}^e\left(\genfrac{}{}{0ex}{}{t}{i}\right)$ satisfies the same recurrence by Pascal’s rule ($\left(\genfrac{}{}{0ex}{}{t}{i}\right)=\left(\genfrac{}{}{0ex}{}{t-1}{i-1}\right)+\left(\genfrac{}{}{0ex}{}{t-1}{i}\right)$, and the $+1$ accounts for the $i=0$ term of the first sum) with the same boundary values $g(0,t)=g(e,0)=0$.

Grid paths with forbidden cells

Paths from $(0,0)$ to $(H,W)$ moving right/down avoiding $K$ forbidden cells ($H,W$ up to $10^5$, $K\le 3000$): sort the cells (and append the target), and let $d{p}_i$ = number of paths from the start to cell $i$ that avoid all earlier forbidden cells:

$d{p}_i=\left(\genfrac{}{}{0ex}{}{x_i+y_i}{x_i}\right)-{\sum }_{j:x_j\le x_i,y_j\le y_i,j\ne i}d{p}_j\left(\genfrac{}{}{0ex}{}{x_i-x_j+y_i-y_j}{x_i-x_j}\right).$

$O(K^2)$ (CF 559C). The same “first bad event” decomposition counts permutations avoiding patterns, sequences avoiding prefix conditions, and lattice paths not touching a set.

Proof: first-forbidden-cell decomposition

Every monotone path to cell $i$ either avoids all forbidden cells (counted by $d{p}_i$) or has a first forbidden cell $j$ it visits. Paths whose first forbidden cell is $j$ are in bijection with (a path to $j$ avoiding forbidden cells, counted by $d{p}_j$) × (any path from $j$ to $i$, a binomial). These classes are disjoint and exhaust all paths to $i$, giving the formula. Sorting by $(x,y)$ ensures every $j$ that can precede $i$ is processed first.

Ordering first, then DP

Many subset-selection problems become knapsack once the right processing order is fixed by an exchange argument:

Problem	Order	DP
jobs with durations $d_i$ and deadlines $D_i$, maximise number/value done	deadline ascending	dp[time] = best value, knapsack with capacity $D_i$ for item $i$
boxes stacked, each with weight $w_i$ and strength $s_i$ (load on it $\le s_i$)	by $s_i+w_i$ descending (top-down)	dp[load]
tasks with requirement $r_i$ and cost $c_i$ (need $\ge r_i$ to start, spend $c_i$)	by $r_i-c_i$ descending	knapsack over remaining resource
nested boxes / envelopes	sort one coordinate	LIS on the other (LIS)

Proof: earliest deadline first is a valid order for any chosen set

Suppose a set of jobs can be scheduled to meet all deadlines, and two consecutive jobs $a,b$ are done with $D_a>D_b$. Swapping them keeps the finishing time of the pair the same; $b$ now finishes earlier, and $a$ finishes at the old finishing time of $b$, which was $\le D_b<D_a$. So both still meet their deadlines. Bubble-sorting by deadline therefore preserves feasibility, and checking a set only in deadline order loses nothing. The other orders follow from the same adjacent-swap computation (for boxes: the pair is safe in order $(a$ above $b)$ iff the load condition holds, and comparing the two orders reduces to comparing $s+w$).

More patterns

• No two adjacent chosen, on a cycle: run the line DP twice, once forcing the first element unused and once forcing the last unused.
• Two simultaneous walkers on a grid (collect values on two disjoint-ish paths): parametrise by step $t$ and both rows, $O(n^3)$; count a shared cell once.
• Maximum-sum submatrix: fix two rows, Kadane over column sums, $O(n^{2}m)$.
• Largest all-ones square: $d{p}_{i,j}=1+\min (d{p}_{i-1,j},d{p}_{i,j-1},d{p}_{i-1,j-1})$; largest rectangle uses histograms (Monotonic Stack).
• DP over prefix with “last occurrence”: number of distinct subsequences, $d{p}_i=2d{p}_{i-1}-d{p}_{\text{last}(s_i)-1}$.
• Max-min segmentation: binary search the answer and check greedily, no DP needed.