Chapter 10

Dynamic programming

Memoisation, tabulation, the 1D/2D patterns, and how to spot DP problems.

Dynamic programming

DP is the topic people find hardest, and the reason is almost always that they try to memorize problems instead of learning to define a state. Once the state and the transition are written down, the code is mechanical. This file is organized by state shape, because that is the thing that transfers.

Every implementation was executed. Where two formulations exist (memoized vs iterative Fibonacci, O(n^2) vs O(n log n) LIS) the tests assert that they agree — including LIS on 50 random arrays.

Table of contents

1. The method

DP applies when a problem has optimal substructure (the optimum is built from optima of subproblems) and overlapping subproblems (the same subproblem recurs). Divide and conquer has the first without the second — which is why merge sort is not DP.

The procedure, in order, every time:

  1. Define the state. What exactly does dp[i] / dp[i][j] mean? Write it as an English sentence. If you cannot, you do not have a DP yet. This is 80% of the work.
  2. Write the recurrence. How does a state depend on smaller states? Enumerate the choices at each state.
  3. Base cases. Usually the empty prefix or a single element. Get the “no items” and “zero capacity” cases right and the rest follows.
  4. Order of evaluation. Top-down (memoized recursion, order handled for you) or bottom-up (you pick an order such that dependencies are already computed).
  5. Complexity = (number of states) x (work per state). Say it in that form.
  6. Space optimization. If dp[i] only reads dp[i-1], you need two rows, or one with the right iteration direction.
  7. Reconstruct the answer if the problem wants the solution and not just its value — either keep a parent/choice table or walk the DP table backwards.

The recognition signals for “this is DP”: count the number of ways, minimum/maximum cost or length, is it possible to reach, optimal partition or subsequence, plus a brute force that would recompute the same subproblem many times. If the greedy choice is provably safe, use greedy instead; if the subproblems do not overlap, use plain recursion or divide and conquer.

2. Memoization vs tabulation

The naive recursive fib(4) call tree below is why memoization helps: fib(2) is recomputed twice and fib(1) three times, and the redundancy compounds exponentially as n grows. A cache turns every highlighted repeat into an O(1) lookup, collapsing the tree into O(n) work.

graph TD
    F4["fib(4)"] --> F3["fib(3)"]
    F4 --> F2b["fib(2)"]
    F3 --> F2a["fib(2)"]
    F3 --> F1c["fib(1)"]
    F2a --> F1a["fib(1)"]
    F2a --> F0a["fib(0)"]
    F2b --> F1b["fib(1)"]
    F2b --> F0b["fib(0)"]
    classDef repeat fill:#f96,stroke:#333,stroke-width:2px
    class F2a,F2b,F1a,F1b,F1c repeat
from functools import cache

def fib_memo(n):
    @cache                                  # top-down: one decorator turns 2^n into O(n)
    def f(k): return k if k < 2 else f(k-1) + f(k-2)
    return f(n)

def fib_iter(n):                            # bottom-up, O(1) space
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

Verified: fib_memo(90) == fib_iter(90) == 2880067194370816120.

Top-down (memoized recursion)Bottom-up (tabulation)
Writing efforttranslate the recurrence literallymust choose a valid evaluation order
Computesonly the states you actually reachevery state in the table
SpaceO(states) + O(recursion depth)O(states), often reducible to O(1 row)
Riskstack overflow (Python ~1000 frames, V8 ~11k)none
Best whenthe state space is sparse or hard to order (grids with pruning, game trees, digit DP)the state space is dense and you want the space optimization

The interview strategy that works: write the recursive brute force first, verify it on the example, add @cache (Python) or a Map (TypeScript), state the complexity, and only then convert to bottom-up if asked about space. That path is far less error-prone than jumping to a table, and it shows your reasoning.

// TypeScript memoization: no @cache, so use a Map with a serialized key.
function memoize<A extends unknown[], R>(fn: (...a: A) => R, key = (...a: A) => a.join(',')) {
  const cache = new Map<string, R>();
  return function self(...a: A): R {
    const k = key(...a);
    if (cache.has(k)) return cache.get(k)!;
    const v = fn(...a);
    cache.set(k, v);
    return v;
  };
}
// For 2D states a nested Map (or a flat array indexed i*n+j) beats string keys in hot loops.

Python’s @cache gotchas, since they bite in interviews: arguments must be hashable (pass tuples, not lists), it holds strong references so caching a method leaks self, and f(1) and f(x=1) are distinct keys. Also, deep recursion still overflows even with the cache — sys.setrecursionlimit or a bottom-up rewrite is the fix.

3. 1D DP: the linear scan family

State: dp[i] = the answer considering the first i elements (or ending exactly at i). Almost all of these collapse to O(1) space because they look back a fixed distance.

def climb(n):
    """Ways to climb n stairs taking 1 or 2 steps. Fibonacci with different base cases."""
    a, b = 1, 1
    for _ in range(n - 1): a, b = b, a + b
    return b

def house_robber(a):
    """Max sum of non-adjacent elements. Two running values: took the last one, or skipped it."""
    take, skip = 0, 0
    for v in a:
        take, skip = skip + v, max(skip, take)
    return max(take, skip)

def house_robber_circular(a):
    """Houses in a circle. Either the first is excluded or the last is — solve both, take the max."""
    if len(a) == 1: return a[0]
    return max(house_robber(a[:-1]), house_robber(a[1:]))

def max_subarray(a):
    """Kadane. dp[i] = max subarray sum ENDING at i = max(a[i], dp[i-1] + a[i])."""
    best = cur = a[0]
    for v in a[1:]:
        cur = max(v, cur + v)               # extend the previous subarray, or start fresh
        best = max(best, cur)
    return best

def max_product_subarray(a):
    """Two states, because a negative number swaps the roles of max and min."""
    best = hi = lo = a[0]
    for v in a[1:]:
        cands = (v, hi * v, lo * v)
        hi, lo = max(cands), min(cands)
        best = max(best, hi)
    return best

def decode_ways(s):
    """'12' -> 'AB' or 'L'. dp[i] = dp[i-1] if s[i] valid alone, + dp[i-2] if the pair is 10..26."""
    if not s or s[0] == '0': return 0
    prev, cur = 1, 1
    for i in range(1, len(s)):
        nxt = 0
        if s[i] != '0': nxt += cur
        if 10 <= int(s[i-1:i+1]) <= 26: nxt += prev
        prev, cur = cur, nxt
    return cur

def word_break(s, words):
    """dp[i] = can s[:i] be segmented? O(n^2) with a set, O(n * maxword) if you bound the inner loop."""
    ws = set(words); n = len(s)
    dp = [False] * (n + 1); dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in ws: dp[i] = True; break
    return dp[n]

Verified: climb(5)==8, house_robber([2,7,9,3,1])==12, circular [2,3,2]==3 and [1,2,3,1]==4, Kadane on the classic array ==6, max_product_subarray([2,3,-2,4])==6, decode_ways("226")==3 and decode_ways("06")==0, and word break both ways.

The pattern in max_product_subarray generalizes: when a transition can flip sign or direction, carry both extremes. The same idea appears in “best time to buy and sell stock with a cooldown” and in any problem where the optimum can come from the pessimum.

The pattern in house_robber generalizes too: two mutually exclusive running states (take / skip) instead of a table. That is a state machine with two nodes — see section 11.

4. The knapsack family

The single most important DP family, because a dozen differently-worded problems are the same recurrence.

State: dp[i][c] = the best value using the first i items with capacity c. The 1D rolling version is what you actually write, and the loop direction encodes the variant.

def knapsack_01(weights, values, cap):
    """Each item at most once. Iterate capacity BACKWARD so dp[c-w] is from the PREVIOUS item."""
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

def knapsack_unbounded(weights, values, cap):
    """Unlimited copies. Iterate capacity FORWARD so dp[c-w] may already include this item."""
    dp = [0] * (cap + 1)
    for c in range(1, cap + 1):
        for w, v in zip(weights, values):
            if w <= c: dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

That loop direction is the single highest-value thing to memorize in this file. Backward = each item used at most once (0/1). Forward = unlimited reuse. Everything else in the family follows.

def coin_change_min(coins, amount):
    """Fewest coins. dp[c] = min over coins of dp[c - coin] + 1. Unbounded, so forward."""
    dp = [0] + [math.inf] * amount
    for c in range(1, amount + 1):
        for coin in coins:
            if coin <= c: dp[c] = min(dp[c], dp[c - coin] + 1)
    return -1 if dp[amount] == math.inf else dp[amount]

def coin_change_ways(coins, amount):
    """Number of COMBINATIONS. Coin loop OUTSIDE -> each multiset counted once."""
    dp = [1] + [0] * amount
    for coin in coins:
        for c in range(coin, amount + 1): dp[c] += dp[c - coin]
    return dp[amount]

def combination_sum_perms(nums, target):
    """Number of PERMUTATIONS. Target loop OUTSIDE -> order matters."""
    dp = [1] + [0] * target
    for t in range(1, target + 1):
        for v in nums:
            if v <= t: dp[t] += dp[t - v]
    return dp[target]

Verified: coin_change_ways([1,2,5], 5) == 4 (the combinations 5, 2+2+1, 2+1+1+1, 1x5) while combination_sum_perms([1,2,3], 4) == 7 (permutations counted separately). Same table, same recurrence, loops swapped, different question answered — this is the classic trap, and being able to explain why is a strong signal: with the item loop outside, a given multiset is only ever built in one canonical order.

def partition_equal_subset(a):
    """Can the array be split into two equal-sum halves? A bitset does the whole DP in one line."""
    s = sum(a)
    if s % 2: return False
    dp = 1                                  # bit i set <=> sum i is reachable
    for v in a: dp |= dp << v               # shifting by v adds v to every reachable sum
    return bool(dp >> (s // 2) & 1)

def target_sum(a, target):
    """Assign +/- to each element to hit target. Reduces to counting subsets summing to
       (total + target) / 2 — which is 0/1 knapsack counting."""
    total = sum(a)
    if (total + target) % 2 or abs(target) > total: return 0
    subset = (total + target) // 2
    dp = [1] + [0] * subset
    for v in a:
        for c in range(subset, v - 1, -1): dp[c] += dp[c - v]   # backward: 0/1
    return dp[subset]

The bitset trick for subset-sum is a genuinely useful Python-specific move: int is an arbitrary-precision bitmask, so dp |= dp << v performs the entire inner loop as one machine-word-parallel operation. It turns an O(n·S) Python loop into O(n·S/64) C-level work, which is often a 20-50x speedup. Verified on [1,5,11,5] (True) and [1,2,3,5] (False).

The family in one table

ProblemVariantLoopObjective
0/1 knapsackeach item oncecapacity backwardmax value
Unbounded knapsack / rod cuttingunlimited copiescapacity forwardmax value
Bounded knapsack (k copies)binary-split into powers of 2, then 0/1backwardmax value
Coin change (min coins)unboundedforwardmin count
Coin change (count ways)unbounded, combinationscoin outsidecount
Combination sum IVunbounded, permutationstarget outsidecount
Subset sum / equal partition0/1backwardreachability (bitset)
Target sum0/1backwardcount
Partition to k equal subsets0/1 + bitmask—feasibility (see section 8)
Last stone weight II0/1, minimize |difference|backwardreachability
Ones and zeroes0/1 with two capacitiesboth backwardmax count

5. Two-sequence DP

State: dp[i][j] = the answer for the first i of A and the first j of B. Complexity is O(m·n) states, O(1) work each. The rolling-row optimization gives O(min(m, n)) space.

def lcs(a, b):
    """Longest common SUBSEQUENCE. Two rows is enough for the length."""
    m, n = len(a), len(b)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        cur = [0] * (n + 1)
        for j in range(1, n + 1):
            cur[j] = prev[j-1] + 1 if a[i-1] == b[j-1] else max(prev[j], cur[j-1])
        prev = cur
    return prev[n]

def lcs_string(a, b):
    """To RECONSTRUCT you need the full table, then walk it backwards."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
    i, j, res = m, n, []
    while i and j:
        if a[i-1] == b[j-1]: res.append(a[i-1]); i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]: i -= 1
        else: j -= 1
    return ''.join(reversed(res))

def edit_distance(a, b):
    """Levenshtein. Three choices: replace (diagonal), delete (up), insert (left)."""
    m, n = len(a), len(b)
    prev = list(range(n + 1))               # base case: delete everything
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            cur[j] = prev[j-1] if a[i-1] == b[j-1] else 1 + min(prev[j-1], prev[j], cur[j-1])
        prev = cur
    return prev[n]

def distinct_subsequences(s, t):
    """How many subsequences of s equal t. 1D, iterate t BACKWARD (0/1 style)."""
    dp = [1] + [0] * len(t)
    for ch in s:
        for j in range(len(t), 0, -1):
            if t[j-1] == ch: dp[j] += dp[j-1]
    return dp[len(t)]

def longest_palindromic_subseq(s):
    """LPS(s) == LCS(s, reversed(s)). One of the nicest reductions in the whole topic."""
    return lcs(s, s[::-1])

Verified: lcs("abcde","ace")==3, lcs_string("abcde","ace")=="ace", edit_distance("horse","ros")==3, edit_distance("intention","execution")==5, distinct_subsequences("rabbbit","rabbit")==3, longest_palindromic_subseq("bbbab")==4.

Longest increasing subsequence — two formulations

def lis_dp(a):
    """O(n^2). dp[i] = LIS ending at i. Easy to extend (count, reconstruct, weighted)."""
    if not a: return 0
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

def lis_patience(a):
    """O(n log n). tails[k] = the smallest possible tail of an increasing subsequence of length k+1.
       Binary search for where this value belongs; the length of `tails` is the answer."""
    tails = []
    for v in a:
        i = bisect_left(tails, v)           # bisect_left -> strictly increasing
        if i == len(tails): tails.append(v) # extends the longest subsequence
        else: tails[i] = v                  # improves the tail of a length-(i+1) subsequence
    return len(tails)

Verified: identical answers on the classic array and on 50 random arrays — the kind of check worth mentioning, because the tails array is famously not itself a valid subsequence, only its length is correct. Use bisect_right for non-decreasing (allowing equal elements).

LIS variants worth knowing: n - LIS is the minimum deletions to sort; the same structure solves “Russian doll envelopes” (sort by width ascending and height descending so equal widths cannot chain), “maximum length of pair chain”, and “minimum number of increasing subsequences to cover” (which is the longest decreasing subsequence, by Dilworth’s theorem).

6. Grid DP

State: dp[r][c] = the answer for the subgrid ending at (r, c). Almost always reducible to one row.

def unique_paths(m, n):
    """Paths from top-left to bottom-right moving right/down. One rolling row."""
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n): dp[j] += dp[j-1]
    return dp[-1]

def unique_paths_obstacles(g):
    m, n = len(g), len(g[0])
    dp = [0] * n; dp[0] = 1 if g[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if g[i][j] == 1: dp[j] = 0                # blocked: zero paths through here
            elif j: dp[j] += dp[j-1]
    return dp[-1]

def min_path_sum(g):
    m, n = len(g), len(g[0])
    dp = [math.inf] * n; dp[0] = 0
    for i in range(m):
        dp[0] += g[i][0]
        for j in range(1, n): dp[j] = min(dp[j], dp[j-1]) + g[i][j]
    return dp[-1]

def maximal_square(m):
    """Largest all-1s square. dp[r][c] = side length ending at (r,c) = 1 + min(up, left, diagonal).
       The rolling version needs an explicit prev_diag variable."""
    R, C = len(m), len(m[0])
    dp = [0] * (C + 1); best = 0
    for r in range(R):
        prev_diag = 0
        for c in range(1, C + 1):
            tmp = dp[c]
            dp[c] = 1 + min(dp[c], dp[c-1], prev_diag) if m[r][c-1] == '1' else 0
            best = max(best, dp[c]); prev_diag = tmp
    return best * best

def longest_increasing_path(matrix):
    """DP on a DAG. Memoized DFS is the right tool: the topological order is implicit."""
    R, C = len(matrix), len(matrix[0])
    @lru_cache(maxsize=None)
    def go(r, c):
        best = 1
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + go(nr, nc))
        return best
    return max(go(r, c) for r in range(R) for c in range(C))

Verified: unique_paths(3,7)==28, obstacles version ==2, min_path_sum==7, maximal_square==4, longest_increasing_path==4.

Two things worth saying about grid DP. The maximal_square prev_diag variable is the general pattern for rolling a 2D DP that needs the diagonal: save the old value before overwriting it. And longest_increasing_path is the case where memoized DFS beats tabulation, because the dependency order is “increasing cell value”, which you would otherwise have to sort by — the recursion discovers it for free. Recognizing when the state graph is a DAG with a non-obvious order is a genuine skill.

7. Interval DP

State: dp[i][j] = the answer for the subarray [i, j]. Evaluate by increasing interval length, because a longer interval depends on shorter ones inside it. O(n^2) states, O(n) work each -> O(n^3).

def matrix_chain(dims):
    """Minimum multiplications to compute A1 x ... x An. dims has n+1 entries.
       Split at every k; cost = left + right + the cost of the final multiply."""
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):                    # interval length, ASCENDING
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                           for k in range(i, j))
    return dp[0][n-1]

def burst_balloons(nums):
    """The trick: think about the LAST balloon burst in an interval, not the first.
       Then its neighbours are exactly the interval's boundaries, which are fixed."""
    a = [1] + nums + [1]; n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j] for k in range(i+1, j))
    return dp[0][n-1]

def palindrome_partition_min_cuts(s):
    """Precompute an is-palindrome table, then a 1D DP over prefixes."""
    n = len(s)
    ispal = [[False] * n for _ in range(n)]
    for i in range(n-1, -1, -1):                      # i descending so ispal[i+1][j-1] is ready
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or ispal[i+1][j-1]): ispal[i][j] = True
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = min((dp[j] + (0 if j == 0 else 1)) for j in range(i) if ispal[j][i-1])
    return dp[n]

Verified: matrix_chain([10,30,5,60])==4500, burst_balloons([3,1,5,8])==167, palindrome_partition_min_cuts("aab")==1.

The “think about the last operation” reframing in burst balloons is the whole lesson of interval DP. The natural formulation (which balloon do I burst first?) does not decompose, because bursting changes the neighbours of everything. Asking which balloon is burst last fixes its neighbours to the interval boundaries, and the two sides become independent. The same reframing solves “minimum cost to merge stones”, “remove boxes”, and “strange printer”.

Other interval DP problems: longest palindromic substring (also solvable by expand-around-center in O(1) space), “minimum score triangulation”, “optimal binary search tree”, and “guess number higher or lower II”.

8. Bitmask DP

State: a subset of up to ~20 elements, encoded as an integer. 2^n states, so n <= 20 is the tell — if the constraint says n <= 20, this is almost certainly the intended solution.

def tsp(dist):
    """Held-Karp travelling salesman. State = (visited set, current city). O(2^n * n^2)."""
    n = len(dist); FULL = (1 << n) - 1
    @lru_cache(maxsize=None)
    def go(mask, v):
        if mask == FULL: return dist[v][0]            # all visited: return home
        best = math.inf
        for nx in range(n):
            if mask >> nx & 1: continue               # already visited
            best = min(best, dist[v][nx] + go(mask | 1 << nx, nx))
        return best
    return go(1, 0)                                   # start at city 0, mask = {0}

def assign_tasks_min_cost(cost):
    """Assignment problem: n workers, n tasks, each worker gets one distinct task.
       State = (worker index, mask of used tasks). The worker index is redundant —
       it equals popcount(mask) — which halves the state space if you drop it."""
    n = len(cost)
    @lru_cache(maxsize=None)
    def go(worker, mask):
        if worker == n: return 0
        return min(cost[worker][t] + go(worker + 1, mask | 1 << t)
                   for t in range(n) if not mask >> t & 1)
    return go(0, 0)

Verified: tsp on the classic 4-city matrix gives 80; assign_tasks_min_cost([[9,2,7],[6,4,3],[5,8,1]]) gives 9 (worker 0 -> task 1 at 2, worker 1 -> task 0 at 6, worker 2 -> task 2 at 1).

The bit operations you need:

mask >> i & 1        is element i in the set?
mask | (1 << i)      add element i
mask & ~(1 << i)     remove element i
mask ^ (1 << i)      toggle element i
mask == (1 << n) - 1 is the set full?
bin(mask).count('1') / mask.bit_count()   size of the set (3.10+)
sub = (sub - 1) & mask                    iterate all SUBSETS of mask (submask enumeration)

Submask enumeration is the technique that makes “partition into k subsets” tractable:

sub = mask
while sub:
    # ... use sub, a submask of mask ...
    sub = (sub - 1) & mask
# total work over all masks: 3^n, not 4^n

Bitmask problems worth recognizing: TSP, assignment, “partition to k equal-sum subsets”, “shortest path visiting all nodes”, “number of ways to wear different hats”, “minimum incompatibility”, and profile DP (broken-profile tiling, where the mask is a column’s occupancy).

9. Tree DP

State: dp[node] = the answer for the subtree rooted at node, usually a tuple of two or three values covering the mutually exclusive cases. Post-order traversal, O(V) total.

def rob_tree(root):
    """House Robber III. Return (rob this node, do not rob this node) — the classic pair state."""
    def go(n):
        if not n: return (0, 0)
        l, r = go(n.l), go(n.r)
        return (n.v + l[1] + r[1],        # rob n -> children must be skipped
                max(l) + max(r))          # skip n -> children are free to choose
    return max(go(root))

def max_path_sum(root):
    """Binary Tree Maximum Path Sum. The path may bend at a node, so track two quantities:
       the best path THROUGH n (for the answer) and the best path ENDING at n (to return upward)."""
    best = [-math.inf]
    def go(n):
        if not n: return 0
        l = max(go(n.l), 0)               # clamp: a negative branch is better skipped
        r = max(go(n.r), 0)
        best[0] = max(best[0], n.v + l + r)
        return n.v + max(l, r)
    go(root)
    return best[0]

Verified: rob_tree on [3,2,3,null,3,null,1] gives 7; max_path_sum on [-10,9,20,null,null,15,7] gives 42.

The two recurring ideas: return a tuple of mutually exclusive cases (rob/skip, matched/unmatched, coloured/uncoloured), and separate the value you report upward from the value you accumulate globally — the path in max_path_sum can bend, so what the parent can use is not what the answer counts.

Related: tree diameter (section 11 of Graphs and trees), “distribute coins in a binary tree”, “binary tree cameras”, maximum independent set on a tree, and rerooting technique (compute the answer for every possible root in O(n) total by combining a down-pass with an up-pass).

10. Digit DP

State: (position, accumulated property, tight) where tight means “the prefix built so far exactly matches the bound’s prefix”, which constrains the current digit’s range. Counts numbers in [0, N] with a property, in O(digits x property-range x 2).

def count_numbers_with_digit_sum(n_str, target):
    """How many x in [0, N] have digit sum exactly == target?"""
    @lru_cache(maxsize=None)
    def go(i, s, tight):
        if s > target: return 0                       # prune: digit sums only grow
        if i == len(n_str): return 1 if s == target else 0
        limit = int(n_str[i]) if tight else 9         # tight -> cannot exceed N's digit
        return sum(go(i + 1, s + d, tight and d == limit) for d in range(limit + 1))
    return go(0, 0, True)

Verified: count_numbers_with_digit_sum("20", 2) == 3 (the numbers 2, 11, 20) and count_numbers_with_digit_sum("100", 1) == 3 (1, 10, 100).

tight and d == limit is the whole trick: once you place a digit strictly below N’s digit, every subsequent position is free (0-9) and the state collapses, which is why the state space stays tiny even for a 10^18 bound. Range queries become f(R) - f(R-1 for the lower bound).

Digit DP covers: “numbers without consecutive ones”, “count numbers with unique digits”, “numbers at most N with digits from a set”, “sum of digits of all numbers up to N”, and “count stepping numbers”. The tell is a bound like 1 <= N <= 10^18 — far too large to iterate, and the answer depends only on the digits.

11. State-machine DP

When the problem has a small number of modes and transitions between them, model it explicitly. This covers the entire “buy and sell stock” family, which otherwise looks like six unrelated problems.

def stock_single(prices):
    """One transaction. Two states: holding, or not."""
    hold, free = -math.inf, 0
    for p in prices:
        hold = max(hold, -p)                  # buy (only from the initial 0 profit)
        free = max(free, hold + p)            # sell
    return free

def stock_unlimited(prices):
    """Unlimited transactions: buying can now start from an existing profit."""
    hold, free = -math.inf, 0
    for p in prices:
        hold, free = max(hold, free - p), max(free, hold + p)
    return free

def stock_with_cooldown(prices):
    """Cannot buy the day after selling: add a third state."""
    hold, sold, rest = -math.inf, -math.inf, 0
    for p in prices:
        hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
    return max(sold, rest)

def stock_k_transactions(prices, k):
    """2k states: for each transaction slot, holding or free. O(n*k)."""
    if not prices or k == 0: return 0
    hold = [-math.inf] * (k + 1)
    free = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            hold[t] = max(hold[t], free[t-1] - p)
            free[t] = max(free[t], hold[t] + p)
    return free[k]

The method: draw the states, draw the transitions, write one line per state. The simultaneous assignment (hold, free = ...) matters in Python — it evaluates the whole right side first, which is exactly the “use the previous day’s values” semantics you want. Writing the two lines sequentially uses today’s hold when computing free, which for stock_unlimited happens to still be correct (it allows a same-day buy-sell, worth 0) but is wrong for the cooldown variant.

Other state-machine DP: “paint house” (colour of the previous house is the state), “delete and earn”, regular-expression / wildcard matching (dp[i][j] with pattern-position states), and any problem phrased as “at most k of X”.

12. Optimizations

Space: rolling arrays. If dp[i] reads only dp[i-1], keep two rows — or one row with the right iteration direction (backward for 0/1 knapsack, forward for unbounded). If it reads the diagonal too, keep one extra scalar (prev_diag in maximal_square).

Space: bitsets. When the DP value is a boolean, pack the whole row into an integer. dp |= dp << v does one entire knapsack row in a handful of machine words. Python’s unbounded int makes this trivial; in JavaScript you would need BigInt or a Uint32Array.

Time: better data structures. LIS goes from O(n^2) to O(n log n) by replacing the inner max-scan with a binary search over tails. The general move: if the transition is dp[i] = max/min over j < i of (something), ask whether a heap, a monotonic deque, a Fenwick tree, or a sorted structure can answer it in O(log n) instead of O(n).

Time: monotonic deque. For dp[i] = max(dp[j] for j in [i-k, i-1]) + a[i], a sliding-window maximum deque makes each step O(1) — “jump game VI”, “constrained subsequence sum”.

Time: prefix sums over the DP table. When the transition sums a contiguous range of previous states, keep a running prefix sum of dp itself.

Time: divide and conquer optimization, Knuth optimization, convex hull trick. These reduce O(n^2) or O(n^3) interval DPs to O(n log n) / O(n^2) when the cost function is monotone or convex. Worth naming in a senior interview; almost never worth implementing in one.

Correctness: iteration order. The most common bug in bottom-up DP. State the dependency (“dp[i][j] needs dp[i-1][j], dp[i][j-1] and dp[i-1][j-1]”) and pick an order that satisfies it, then double-check the boundary row and column.

13. Test run

  ok  1D DP: fib (memo==iter), climbing stairs, house robber (+circular), Kadane, max product,
      decode ways, word break
  ok  knapsack family: 0/1 (backward loop), unbounded, coin-change min/ways, perms vs combos,
      subset partition (bitset), target sum
  ok  subsequences: LCS (+reconstruct), LIS O(n^2) == LIS O(n log n) on 50 random arrays,
      edit distance, distinct subseq, LPS
  ok  grid DP: unique paths (+obstacles), min path sum, maximal square (rolling row),
      longest increasing path (memo DFS)
  ok  interval DP: matrix chain, burst balloons (think last, not first), palindrome partition cuts,
      LPSubstring
  ok  bitmask DP: held-karp TSP (n=4 -> 80), subset enumeration, assignment problem
  ok  tree DP: house robber III (rob/skip pair), binary tree max path sum
  ok  digit DP: count numbers in [0,n] with a given digit sum, via (index, sum, tight) state

ALL DP ASSERTIONS PASSED (8 families)

14. Interview questions

Q: How do you know a problem is DP?

A: Optimal substructure plus overlapping subproblems, usually signalled by “count the ways”, “min/max cost”, or “is it reachable”, together with a brute force that recomputes the same subproblem. If a locally optimal choice is provably safe, it is greedy instead; if subproblems do not overlap, it is plain divide and conquer.

Q: Memoization or tabulation?

A: Memoization to get a correct solution fast and to skip unreachable states; tabulation when you want the O(1)-row space optimization or when recursion depth is a risk. In an interview: recursive brute force, add a cache, then convert if asked.

Q: What is the complexity of a DP?

A: States x work per state. Say it in that form — “O(n·W) states, O(1) transition, so O(n·W) time and O(W) space after the rolling optimization”.

Q: Why does 0/1 knapsack iterate capacity backwards?

A: So that dp[c - w] still refers to the previous item’s row. Forward iteration would let the same item be picked twice, which is exactly the unbounded variant. That one loop direction is the difference between the two problems.

Q: Coin change: why do the loop orders give different answers?

A: With the coin loop outside, each multiset of coins is built in exactly one canonical order, so you count combinations. With the target loop outside, every ordering is counted separately, so you count permutations. Verified: coin_change_ways([1,2,5],5)==4 but combination_sum_perms([1,2,3],4)==7.

Q: Explain the O(n log n) LIS.

A: tails[k] is the smallest possible tail value of an increasing subsequence of length k+1. For each element, binary search for its position: if it extends the longest run, append; otherwise it improves an existing tail. len(tails) is the LIS length — but tails itself is not a valid subsequence, which is the follow-up people miss.

Q: Reconstruct the actual subsequence, not just its length.

A: Keep the full DP table (or a parent pointer per state) and walk backwards from the final state, choosing the predecessor that produced the optimum. For LIS with the O(n log n) method, store each element’s position in tails plus a predecessor index.

Q: How do you optimize DP space?

A: If row i depends only on row i-1, keep two rows, or one with the correct iteration direction. If it also needs the diagonal, keep one scalar. If the values are boolean, pack a row into an integer bitset.

Q: How would you do DP in TypeScript without Python’s @cache?

A: A Map keyed on a serialized state, wrapped in a memoize helper. For 2D states prefer a nested Map or a flat typed array indexed i * n + j — string keys allocate and hash on every call, which matters inside a hot DP.

Q: Burst balloons — why is “which balloon first” the wrong question?

A: Bursting changes the neighbours of every remaining balloon, so the subproblems are not independent. Asking which balloon is burst last fixes its neighbours to the interval boundaries, and the left and right intervals become independent. Same reframing for “minimum cost to merge stones”.

Q: When does memoized DFS beat tabulation?

A: When the dependency order is not a simple index sweep. “Longest increasing path in a matrix” depends on cell values, so tabulation would require sorting the cells first; recursion discovers the order for free. Also when the reachable state space is much smaller than the full table.

Q: What is the state for the stock problems?

A: (day, transactions used, holding or not). Unlimited transactions collapses to two running values; a cooldown adds a third state; “at most k” needs 2k states. Writing it as a state machine turns six LeetCode problems into one template.

Q: How do you handle DP with a huge numeric bound, like N up to 10^18?

A: Digit DP: state is (digit position, accumulated property, tight). Once a digit is placed strictly below the bound’s digit, the rest are unconstrained, so the state space is tiny.

Q: When is bitmask DP appropriate?

A: When the state is a subset of a small set — the constraint n <= 20 is the tell. 2^n states, and transitions are bit operations. Submask enumeration sub = (sub-1) & mask gives 3^n total work over all masks, which is what makes “partition into k subsets” feasible.

Q: Tree DP — what does the recursion return?

A: A tuple of mutually exclusive cases for the subtree (rob/skip, matched/unmatched). Keep the value you report upward separate from the value you accumulate globally when the optimal structure can bend at a node, as in maximum path sum.

Q: How do you avoid the most common bottom-up bug?

A: Write the dependency out loud before the loops — “dp[i][j] needs dp[i-1][j], dp[i][j-1] and dp[i-1][j-1]” — then pick an iteration order that satisfies it, and initialize the boundary row and column explicitly rather than relying on defaults.

Q: Give an example where the greedy is wrong and DP is needed.

A: Coin change with [1,3,4] and target 6: greedy takes 4+1+1 = 3 coins, optimum is 3+3 = 2. Also 0/1 knapsack, LIS, and edit distance.

Q: How does LPS relate to LCS?

A: Longest palindromic subsequence of s equals LCS(s, reverse(s)). One of the cleanest reductions in the topic, and it means you only need to remember one algorithm.

Q: Can you always convert top-down to bottom-up?

A: Yes when the state space is finite and you can find a valid topological order of the dependencies. It is not always worth it: if most states are unreachable, or the order is awkward (grid path problems ordered by cell value), memoized recursion is both faster and clearer.

Q: What is the difference between DP and divide and conquer?

A: Overlapping subproblems. Merge sort’s halves are disjoint, so there is nothing to memoize. Fibonacci’s recursive calls overlap massively, so there is.

Q: What is Kadane’s algorithm, in state terms?

A: dp[i] = maximum subarray sum ending at i = max(a[i], dp[i-1] + a[i]). The answer is the max over all i. Defining the state as “ending at i” rather than “within the first i” is what makes the recurrence O(1).

Next: Problem sets to drill these, or the cheat sheets for the quick reference.

Verify it yourself

dp/d.py

from functools import lru_cache, cache
from bisect import bisect_left
import math
out=[]
def ok(m): out.append("  ok  "+m)

# ---------- 1D ----------
def fib_memo(n):
    @cache
    def f(k): return k if k<2 else f(k-1)+f(k-2)
    return f(n)
def fib_iter(n):
    a,b=0,1
    for _ in range(n): a,b=b,a+b
    return a
def climb(n):
    a,b=1,1
    for _ in range(n-1): a,b=b,a+b
    return b
def house_robber(a):
    take, skip = 0, 0
    for v in a: take, skip = skip+v, max(skip, take)
    return max(take, skip)
def house_robber_circular(a):
    if len(a)==1: return a[0]
    return max(house_robber(a[:-1]), house_robber(a[1:]))
def max_subarray(a):                       # Kadane
    best = cur = a[0]
    for v in a[1:]:
        cur = max(v, cur+v); best = max(best, cur)
    return best
def max_product_subarray(a):
    best = hi = lo = a[0]
    for v in a[1:]:
        cands = (v, hi*v, lo*v)
        hi, lo = max(cands), min(cands)
        best = max(best, hi)
    return best
def decode_ways(s):
    if not s or s[0]=='0': return 0
    prev, cur = 1, 1
    for i in range(1,len(s)):
        nxt = 0
        if s[i] != '0': nxt += cur
        if 10 <= int(s[i-1:i+1]) <= 26: nxt += prev
        prev, cur = cur, nxt
    return cur
def word_break(s, words):
    ws=set(words); n=len(s)
    dp=[False]*(n+1); dp[0]=True
    for i in range(1,n+1):
        for j in range(i):
            if dp[j] and s[j:i] in ws: dp[i]=True; break
    return dp[n]
assert fib_memo(90)==fib_iter(90)==2880067194370816120
assert climb(5)==8 and house_robber([2,7,9,3,1])==12
assert house_robber_circular([2,3,2])==3 and house_robber_circular([1,2,3,1])==4
assert max_subarray([-2,1,-3,4,-1,2,1,-5,4])==6
assert max_product_subarray([2,3,-2,4])==6 and max_product_subarray([-2,0,-1])==0
assert decode_ways("226")==3 and decode_ways("06")==0 and decode_ways("11106")==2
assert word_break("leetcode",["leet","code"]) and not word_break("catsandog",["cats","dog","sand","and","cat"])
ok("1D DP: fib (memo==iter), climbing stairs, house robber (+circular), Kadane, max product, decode ways, word break")

# ---------- knapsack family ----------
def knapsack_01(weights, values, cap):
    dp=[0]*(cap+1)
    for w,v in zip(weights,values):
        for c in range(cap, w-1, -1):        # BACKWARD: each item used at most once
            dp[c]=max(dp[c], dp[c-w]+v)
    return dp[cap]
def knapsack_unbounded(weights, values, cap):
    dp=[0]*(cap+1)
    for c in range(1,cap+1):
        for w,v in zip(weights,values):
            if w<=c: dp[c]=max(dp[c], dp[c-w]+v)
    return dp[cap]
def coin_change_min(coins, amount):
    dp=[0]+[math.inf]*amount
    for c in range(1,amount+1):
        for coin in coins:
            if coin<=c: dp[c]=min(dp[c], dp[c-coin]+1)
    return -1 if dp[amount]==math.inf else dp[amount]
def coin_change_ways(coins, amount):
    dp=[1]+[0]*amount
    for coin in coins:                       # coin loop OUTSIDE -> COMBINATIONS
        for c in range(coin, amount+1): dp[c]+=dp[c-coin]
    return dp[amount]
def combination_sum_perms(nums, target):
    dp=[1]+[0]*target
    for t in range(1,target+1):              # target loop OUTSIDE -> PERMUTATIONS
        for v in nums:
            if v<=t: dp[t]+=dp[t-v]
    return dp[target]
def partition_equal_subset(a):
    s=sum(a)
    if s%2: return False
    target=s//2
    dp=1                                     # bitset DP: bit i set means sum i is reachable
    for v in a: dp |= dp << v
    return bool(dp >> target & 1)
def target_sum(a, target):
    total=sum(a)
    if (total+target)%2 or abs(target)>total: return 0
    subset=(total+target)//2
    dp=[1]+[0]*subset
    for v in a:
        for c in range(subset, v-1, -1): dp[c]+=dp[c-v]
    return dp[subset]
assert knapsack_01([1,3,4,5],[1,4,5,7],7)==9
assert knapsack_unbounded([1,3,4],[1,4,5],7)==9
assert coin_change_min([1,3,4],6)==2 and coin_change_min([2],3)==-1
assert coin_change_ways([1,2,5],5)==4
assert combination_sum_perms([1,2,3],4)==7
assert partition_equal_subset([1,5,11,5]) and not partition_equal_subset([1,2,3,5])
assert target_sum([1,1,1,1,1],3)==5
ok("knapsack family: 0/1 (backward loop), unbounded, coin-change min/ways, perms vs combos, subset partition (bitset), target sum")

# ---------- subsequences ----------
def lcs(a,b):
    m,n=len(a),len(b)
    prev=[0]*(n+1)
    for i in range(1,m+1):
        cur=[0]*(n+1)
        for j in range(1,n+1):
            cur[j] = prev[j-1]+1 if a[i-1]==b[j-1] else max(prev[j], cur[j-1])
        prev=cur
    return prev[n]
def lcs_string(a,b):
    m,n=len(a),len(b)
    dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            dp[i][j] = dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j], dp[i][j-1])
    i,j,res=m,n,[]
    while i and j:
        if a[i-1]==b[j-1]: res.append(a[i-1]); i-=1; j-=1
        elif dp[i-1][j] >= dp[i][j-1]: i-=1
        else: j-=1
    return ''.join(reversed(res))
def lis_dp(a):
    if not a: return 0
    dp=[1]*len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j]<a[i]: dp[i]=max(dp[i], dp[j]+1)
    return max(dp)
def lis_patience(a):
    tails=[]
    for v in a:
        i=bisect_left(tails,v)
        if i==len(tails): tails.append(v)
        else: tails[i]=v
    return len(tails)
def edit_distance(a,b):
    m,n=len(a),len(b)
    prev=list(range(n+1))
    for i in range(1,m+1):
        cur=[i]+[0]*n
        for j in range(1,n+1):
            cur[j] = prev[j-1] if a[i-1]==b[j-1] else 1+min(prev[j-1], prev[j], cur[j-1])
        prev=cur
    return prev[n]
def distinct_subsequences(s,t):
    dp=[1]+[0]*len(t)
    for ch in s:
        for j in range(len(t),0,-1):
            if t[j-1]==ch: dp[j]+=dp[j-1]
    return dp[len(t)]
def longest_palindromic_subseq(s): return lcs(s, s[::-1])
assert lcs("abcde","ace")==3 and lcs_string("abcde","ace")=="ace"
assert lis_dp([10,9,2,5,3,7,101,18])==4==lis_patience([10,9,2,5,3,7,101,18])
import random
for _ in range(50):
    arr=[random.randint(0,20) for _ in range(random.randint(0,15))]
    assert lis_dp(arr)==lis_patience(arr) if arr else True
assert edit_distance("horse","ros")==3 and edit_distance("intention","execution")==5
assert distinct_subsequences("rabbbit","rabbit")==3
assert longest_palindromic_subseq("bbbab")==4
ok("subsequences: LCS (+reconstruct), LIS O(n^2) == LIS O(n log n) on 50 random arrays, edit distance, distinct subseq, LPS")

# ---------- grid ----------
def unique_paths(m,n):
    dp=[1]*n
    for _ in range(1,m):
        for j in range(1,n): dp[j]+=dp[j-1]
    return dp[-1]
def unique_paths_obstacles(g):
    m,n=len(g),len(g[0])
    dp=[0]*n; dp[0]=1 if g[0][0]==0 else 0
    for i in range(m):
        for j in range(n):
            if g[i][j]==1: dp[j]=0
            elif j: dp[j]+=dp[j-1]
    return dp[-1]
def min_path_sum(g):
    m,n=len(g),len(g[0])
    dp=[math.inf]*n; dp[0]=0
    for i in range(m):
        dp[0]+=g[i][0]
        for j in range(1,n): dp[j]=min(dp[j],dp[j-1])+g[i][j]
    return dp[-1]
def maximal_square(m):
    R,C=len(m),len(m[0])
    dp=[0]*(C+1); best=0; prev_diag=0
    for r in range(R):
        prev_diag=0
        for c in range(1,C+1):
            tmp=dp[c]
            dp[c] = 1+min(dp[c], dp[c-1], prev_diag) if m[r][c-1]=='1' else 0
            best=max(best,dp[c]); prev_diag=tmp
    return best*best
def longest_increasing_path(matrix):
    R,C=len(matrix),len(matrix[0])
    @lru_cache(maxsize=None)
    def go(r,c):
        best=1
        for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr,nc=r+dr,c+dc
            if 0<=nr<R and 0<=nc<C and matrix[nr][nc]>matrix[r][c]:
                best=max(best,1+go(nr,nc))
        return best
    return max(go(r,c) for r in range(R) for c in range(C))
assert unique_paths(3,7)==28
assert unique_paths_obstacles([[0,0,0],[0,1,0],[0,0,0]])==2
assert min_path_sum([[1,3,1],[1,5,1],[4,2,1]])==7
assert maximal_square([list("10100"),list("10111"),list("11111"),list("10010")])==4
assert longest_increasing_path([[9,9,4],[6,6,8],[2,1,1]])==4
ok("grid DP: unique paths (+obstacles), min path sum, maximal square (rolling row), longest increasing path (memo DFS)")

# ---------- intervals / partition ----------
def matrix_chain(dims):
    n=len(dims)-1
    dp=[[0]*n for _ in range(n)]
    for length in range(2,n+1):
        for i in range(n-length+1):
            j=i+length-1
            dp[i][j]=min(dp[i][k]+dp[k+1][j]+dims[i]*dims[k+1]*dims[j+1] for k in range(i,j))
    return dp[0][n-1]
def burst_balloons(nums):
    a=[1]+nums+[1]; n=len(a)
    dp=[[0]*n for _ in range(n)]
    for length in range(2,n):
        for i in range(n-length):
            j=i+length
            dp[i][j]=max(dp[i][k]+dp[k][j]+a[i]*a[k]*a[j] for k in range(i+1,j))
    return dp[0][n-1]
def palindrome_partition_min_cuts(s):
    n=len(s)
    ispal=[[False]*n for _ in range(n)]
    for i in range(n-1,-1,-1):
        for j in range(i,n):
            if s[i]==s[j] and (j-i<2 or ispal[i+1][j-1]): ispal[i][j]=True
    dp=[0]*(n+1)
    for i in range(1,n+1):
        dp[i]=min((dp[j] + (0 if j==0 else 1)) for j in range(i) if ispal[j][i-1])
    return dp[n]
def longest_palindromic_substring_dp(s):
    n=len(s)
    if not n: return ""
    best=(0,0)
    ispal=[[False]*n for _ in range(n)]
    for i in range(n-1,-1,-1):
        for j in range(i,n):
            if s[i]==s[j] and (j-i<2 or ispal[i+1][j-1]):
                ispal[i][j]=True
                if j-i > best[1]-best[0]: best=(i,j)
    return s[best[0]:best[1]+1]
assert matrix_chain([10,30,5,60])==4500
assert burst_balloons([3,1,5,8])==167
assert palindrome_partition_min_cuts("aab")==1
assert longest_palindromic_substring_dp("babad") in ("bab","aba")
ok("interval DP: matrix chain, burst balloons (think last, not first), palindrome partition cuts, LPSubstring")

# ---------- bitmask ----------
def tsp(dist):
    n=len(dist); FULL=(1<<n)-1
    @lru_cache(maxsize=None)
    def go(mask,v):
        if mask==FULL: return dist[v][0]
        best=math.inf
        for nx in range(n):
            if mask>>nx & 1: continue
            best=min(best, dist[v][nx]+go(mask|1<<nx, nx))
        return best
    return go(1,0)
def count_bits_subsets_sum(nums, target):
    n=len(nums)
    return sum(1 for m in range(1<<n) if sum(nums[i] for i in range(n) if m>>i&1)==target)
def assign_tasks_min_cost(cost):
    """cost[worker][task]; assign each worker a distinct task minimizing total."""
    n=len(cost)
    @lru_cache(maxsize=None)
    def go(worker, mask):
        if worker==n: return 0
        return min(cost[worker][t] + go(worker+1, mask|1<<t) for t in range(n) if not mask>>t&1)
    return go(0,0)
assert tsp([[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]])==80
assert count_bits_subsets_sum([1,2,3,4],5)==2
assert assign_tasks_min_cost([[9,2,7],[6,4,3],[5,8,1]])==9   # w0->t1(2), w1->t0(6), w2->t2(1)
ok("bitmask DP: held-karp TSP (n=4 -> 80), subset enumeration, assignment problem")

# ---------- tree DP ----------
class TN:
    __slots__=("v","l","r")
    def __init__(self,v,l=None,r=None): self.v=v;self.l=l;self.r=r
def rob_tree(root):
    def go(n):
        if not n: return (0,0)               # (rob this node, skip this node)
        l, r = go(n.l), go(n.r)
        return (n.v + l[1] + r[1], max(l) + max(r))
    return max(go(root))
def max_path_sum(root):
    best=[-math.inf]
    def go(n):
        if not n: return 0
        l=max(go(n.l),0); r=max(go(n.r),0)   # clamp negatives to 0: skip that branch
        best[0]=max(best[0], n.v+l+r)
        return n.v+max(l,r)
    go(root); return best[0]
t=TN(3,TN(2,None,TN(3)),TN(3,None,TN(1)))
assert rob_tree(t)==7
assert max_path_sum(TN(-10,TN(9),TN(20,TN(15),TN(7))))==42
ok("tree DP: house robber III (rob/skip pair), binary tree max path sum")

# ---------- digit DP ----------
def count_numbers_with_digit_sum(n_str, target):
    """How many x in [0, n] have digit sum == target? Classic digit DP."""
    @lru_cache(maxsize=None)
    def go(i, s, tight):
        if s > target: return 0
        if i == len(n_str): return 1 if s == target else 0
        limit = int(n_str[i]) if tight else 9
        return sum(go(i+1, s+d, tight and d == limit) for d in range(limit+1))
    return go(0,0,True)
assert count_numbers_with_digit_sum("20",2)==3       # 2, 11, 20
assert count_numbers_with_digit_sum("100",1)==3      # 1, 10, 100
ok("digit DP: count numbers in [0,n] with a given digit sum, via (index, sum, tight) state")

print("\n".join(out)); print(f"\nALL DP ASSERTIONS PASSED ({len(out)} families)")