1D DP Pattern Hub

Track `minPrice` seen so far; at each day `p`, candidate profit is `p - minPrice`.

Ways to reach step `i` equals `dp[i-1] + dp[i-2]` (arrive via 1-step or 2-step hop). Collapse the DP table to two rolling scalar variables `prev, curr`.

Bottom-up unbounded knapsack minimizing `dp[a]` (min coins for amount `a`). Initialize `dp = [amount + 1] * (amount + 1)` with `dp[0] = 0`, iterate `c` then `a >= c`: `dp[a] = min(dp[a], 1 + dp[a - c])`.

At index `i`, zero yields `0` single-digit decodings (`"0"` is invalid standalone). Otherwise inherit `dp[i+1]` (1-digit `1..9`) plus `dp[i+2]` whenever `s[i:i+2]` lies in `10..26`.

At house `x`, either skip (`rob2`) or rob `x` + best two houses back (`rob1 + x`). Recurrence `nxt = max(rob2, rob1 + x)` collapses strictly into two rolling variables.

Since house `0` and `n-1` are adjacent in a circle, they cannot both be robbed. Split into two linear House Robber subproblems excluding either endpoint: `max(nums[0], linear(nums[:-1]), linear(nums[1:]))`.

Patience sorting (`tails` invariant): maintain `tails[k]` = smallest possible tail value of any strictly increasing subsequence of length `k + 1`. Because `tails` stays strictly sorted, replace the first element `>= x` via `bisect_left` (or append when `x` exceeds all tails).

Expand outward from every odd (`(i, i)`) and even (`(i, i + 1)`) center in O(1) extra space, tracking `[bestStart, bestLen]` rather than allocating substrings on every expansion.

Because multiplying by a negative swaps maximum and minimum signs (and multiplying by `0` resets products), track **both** `(curMax, curMin)` ending at `i`: update simultaneously against `x`, `curMax * x`, and `curMin * x`.

Kadane’s Algorithm: any negative running prefix sum only lowers subsequent subarrays. Either extend the current subarray (`cur + x`) or start fresh at `x`: `cur = max(x, cur + x)`, `best = max(best, cur)`.

Define `dp[i] = True` iff prefix `s[:i]` can be segmented. Instead of checking every split `0..i`, probe each word `w` in `wordDict` backward from `i` (`dp[i - len(w)] and s[i-len(w):i] == w`) with a hash set or bounded lengths.