2D DP Pattern Hub

Three-state machine on day `i`: `hold` (currently holding share), `sold` (just sold today -> enters cooldown tomorrow), `rest` (not holding, cooled off). Transitions: `hold = max(hold, rest - p)`, `rest = max(rest, sold)`, `sold = prev_hold + p`.

To count **combinations** (order-independent, `[1,2]` == `[2,1]`), place the **coin loop on the outside** and `amount` loop on the inside (`dp[a] += dp[a - c]`). Putting `amount` outside counts *permutations* instead.

Levenshtein recurrence on rolling 1D row: if `w1[i] == w2[j]`, inherit `diag`; otherwise `1 + min(dp[j] /*delete*/, dp[j-1] /*insert*/, diag /*replace*/)`. Remember `dp[0] = i` on each row start.

Check `len(s1) + len(s2) == len(s3)` first. State `(i, j)` tracks whether `s1[:i]` and `s2[:j]` interleave to form `s3[:i + j]`. Rolling 1D row: `dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])`.

Rolling 1D DP tracking previous diagonal `diag`: if `text1[i] == text2[j]`, extend `diag + 1`; otherwise `max(dp[j], dp[j - 1])`. Space drops from `O(M * N)` to `O(min(M, N))`.

Strictly increasing edges `matrix[nr][nc] > matrix[r][c]` guarantee the implicit graph is a **DAG** (no cycles are possible!). Therefore no `visited` set is needed — plain memoized DFS (`cache[r][c]`) computes every cell’s longest path once.

Algebraic reduction to 0/1 Subset Sum: partition `nums` into positive `P` and negative `N` subsets: `P - N = target` and `P + N = total`, so `P = (total + target) / 2`. Count subsets summing to `P` with backward 0/1 knapsack `dp[s] += dp[s - x]`.

Rolling 1D row of width `n` initialized to `1`: `dp[j] += dp[j - 1]` combines ways from top (`prev dp[j]`) and left (`updated dp[j-1]`). Or closed-form binomial `C(m + n - 2, min(m, n) - 1)`.