Dynamic Programming

Compress histories only when their futures agree

For a sequence-prefix problem, the remaining index may determine the rest. For a capacity problem, remaining capacity also matters. For constrained trading, whether an asset is held and whether a cooldown applies can change legal future actions.

If two histories reach the same state, the stored summary must represent what the parent needs: feasibility, a count, a minimum cost or a maximum value. Enumerating all distinct outputs still has output cost; a memoized optimum is not an enumeration of every route.

Choose greedy only when one summary provably dominates the discarded alternatives. DP retains alternatives when locally inferior choices can have different future consequences. Backtracking instead explores and restores path choices, possibly with pruning; adding memoization requires a sufficient cache key.

State, transitions, bases, order and answer

“At index i” differs from “using the first i elements.” Prefix states usually include an empty-prefix row or cell. For exact filling, an unreachable capacity needs −∞ or another failure sentinel; initializing every cell to zero would falsely claim every exact capacity is reachable.

Counting often uses one way to construct the empty object, while minimum cost uses zero cost for the empty object. Other states start as impossible. These neutral values follow the operation being combined, not a universal “fill with zero” rule.

Memoization and tabulation evaluate the same states

Top-down memoization follows the recursive query and caches complete results by state. It often computes only reachable states. Bottom-up tabulation follows an explicit dependency order and can avoid recursion overhead.

# Pseudocode: define the domain-specific pieces first.
from functools import cache
@cache
def solve(state):
    if is_base(state):
        return base_value(state)
    return combine(solve(previous)
                   for previous in predecessors(state))

The cache must include every parameter affecting the result. Mutable global inputs can invalidate a reused cache. Recursion needs a well-founded dependency or another solving method; cycles are not resolved merely by adding a cache after return.

View repeated calls as a decision tree whose equivalent states merge into a dependency graph. Evaluate an acyclic recurrence in dependency order. Topological and bounded-edge paths → use exactly this discipline.

Small previous summaries can be sufficient

For nonadjacent selections, let best[i] mean the optimum using the first i values, with selecting none allowed. Set best[0]=0 and, when a value exists, best[1]=max(0,value[0]). For i≥2, best[i]=max(best[i−1], best[i−2]+value[i−1]). Separate “skip” from “take plus compatible prefix.” Negative values are skipped under this contract; requiring a nonempty selection changes the bases.

A circular sequence additionally forbids taking both endpoints. Solve the two linear cases excluding one endpoint each, with explicit empty/singleton behavior. The circle does not disappear by using the linear recurrence unchanged.

State can include several small modes: hold/not-hold/cooldown or a pending decoding condition. The number of indices in the source text does not by itself determine the number of needed state variables.

A prefix ends with one valid piece

Each possible last piece is a transition from an already feasible prefix. A short greedy piece can block a later segmentation, so prefix feasibility retains alternatives. Parent pointers can reconstruct one successful partition if needed.

def word_break(text, words):
    dictionary = set(words)
    feasible = [False] * (len(text) + 1)
    feasible[0] = True
    for end in range(1, len(text) + 1):
        for start in range(end):
            if feasible[start] and text[start:end] in dictionary:
                feasible[end] = True
                break
    return feasible[-1]

Dictionary membership is cheap only after a key exists. Creating and hashing a substring can add length-dependent work to the nominal O(n²) candidate transitions. Limit candidate lengths or use prefix structures when that cost matters.

Digit decoding also has one-piece/two-piece transitions, but validity depends on the digit alphabet and leading zeros. Empty-prefix counting and invalid-zero transitions must be explicit. Palindrome partitioning can precompute a valid-piece table before exploring or minimizing cuts.

Reuse versus one-use choices

A one-dimensional implementation must read the correct layer. Decreasing capacities preserve an old smaller-capacity value for a 0/1 update. Increasing capacities allow the current item to be reused through a newly updated smaller capacity.

For minimum coins, amount zero costs zero and unreachable amounts start at infinity. An unbounded recurrence can read a smaller amount repeatedly. For counting, coin-outer/amount-increasing loops count combinations under a distinct-positive-denomination contract. Amount-outer/coin-inner loops generally count ordered sequences instead.

Duplicate denominations can double-count types unless intentionally distinguished. Zero or negative denominations break the simple increasing-amount dependency and need a different contract. A sum table up to integer W is pseudopolynomial O(nW), not polynomial in the bit length of W.

Sequence state is not necessarily substring state

This recurrence takes O(n²) comparisons. A tails representation plus binary search can reach O(n log n) length computation. Each tails slot is the smallest achievable ending value at that length; the slots themselves need not be one valid output subsequence.

Strictly increasing uses a lower-bound replacement rule; a nondecreasing variant changes equality handling. Reconstruction needs predecessor and position information. Subsequence selection can skip characters; a substring must remain contiguous.

A grid position determines the remaining moves

A right/down grid-path count sums contributions from valid upper/left predecessors. Obstacles reset a cell to zero; an empty grid or blocked start needs explicit handling. A longest increasing grid path uses a value-increasing dependency, not an arbitrary row-major order.

def unique_paths(rows, columns):
    if type(rows) is not int or type(columns) is not int:
        raise ValueError("dimensions must be integers")
    if rows < 0 or columns < 0:
        raise ValueError("dimensions must be nonnegative")
    if rows == 0 or columns == 0:
        return 0
    paths = [[1] * columns for _ in range(rows)]
    for row in range(1, rows):
        for column in range(1, columns):
            paths[row][column] = paths[row - 1][column] + paths[row][column - 1]
    return paths[-1][-1]

Two changing prefixes need a grid

Matching final characters extend a common subsequence from the shorter prefixes. Different final characters require dropping one side or the other. LCS does not require those matched characters to be adjacent.

def lcs_prefix(a, b):
    lengths = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                lengths[i][j] = 1 + lengths[i - 1][j - 1]
            else:
                lengths[i][j] = max(lengths[i - 1][j], lengths[i][j - 1])
    return lengths[-1][-1]

def lcs_suffix(a, b):
    lengths = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) - 1, -1, -1):
        for j in range(len(b) - 1, -1, -1):
            if a[i] == b[j]:
                lengths[i][j] = 1 + lengths[i + 1][j + 1]
            else:
                lengths[i][j] = max(lengths[i + 1][j], lengths[i][j + 1])
    return lengths[0][0]

Choose one state contract before writing the loops. Mixing suffix dependencies with forward prefix loops reads unfinished cells.

Edit operations move different coordinates

For unit-cost edit distance turning a[:i] into b[:j], bases are edit[i,0]=i and edit[0,j]=j. Equal last characters use the diagonal unchanged. Otherwise take one plus the minimum of delete edit[i−1,j], insert edit[i,j−1] and replace edit[i−1,j−1].

Dropping the replace branch changes the allowed operation set. Weighted edits change transition costs. Strings may be sequences of code points, bytes or grapheme clusters; choose the unit before claiming a distance.

Interleaving strings uses two consumed-prefix lengths with a third position determined by their sum. Counting distinct subsequences adds skip and matching-use branches. Pattern matching also needs the pattern operator's semantics; a star transition cannot be inferred from LCS's two skip branches.

Intervals need their own evaluation order

When a state is a substring or interval (left,right), solve shorter intervals before longer ones if the recurrence depends on interiors. Palindrome validity combines endpoint equality with the inner interval's validity; one- and two-character bases avoid invalid reads.

A splitting recurrence can try every midpoint inside an interval, giving O(n³) work across O(n²) states. For elimination rewards, choosing the last removed interior object can make surviving boundary values fixed. Choosing the first removal leaves changing neighbors and often fails to isolate independent subproblems.

Do not label every two-coordinate state “O(n²).” The number and cost of transitions per state determine time. Reconstruction and output size can require extra memory even when only the optimum fits a compressed table.

Reduce memory without changing versioned dependencies

If a row depends only on the previous row, two rows may suffice. A single-row LCS/edit implementation must preserve the old diagonal before overwriting it. “Above” is the old row value; “left” may be the current row's newly computed value.

0/1 capacity updates decrease; reusable-item updates increase. Grid sums moving right intentionally reuse current-row left state. These are consequences of each recurrence, not a universal direction preference.

Compute a clear full-table reference first, then compare the compressed result on small cases. Also test whether the compressed state can still support the requested reconstructed solution.

Count states and transition work

Bound runtime by summing actual transition costs over evaluated states. A maximum transition cost times the state count gives an upper bound, not a universal exact runtime. Peak memory counts simultaneously live table entries, recursion frames and reconstruction/output storage; avoid counting shared allocations twice. Include string creation, hashing, arithmetic and copying when they are not constant-cost operations.

Test an empty prefix, impossible state, one item, repeated values, negative values where allowed, an exact-versus-at-most distinction and a case where an ascending loop reuses an item accidentally.

Write the meaning of every cell in one sentence. Check dependencies and base cases before space optimization. Subtree return contracts → provide the same discipline without repeated-state caching.

Related state models

Bounded-edge paths → separate transition layers. Tree return contracts → define what a parent receives. Backtracking → preserves path choices when a small sufficient state is not available.

The labs are exact small recurrences, not measured training curves or runtime comparisons.