Backtracking and dynamic programming

Before this lesson: lesson 02 (binary search, greedy choices) and lesson 03 (DFS, DAGs, topological order, shortest paths). Time: about 80 minutes, plus the notebook.

Why this matters #

DP rounds test one skill: say the state and the recurrence before you code. Most lost time comes from base cases, loop order and off-by-one prefix indices, so this lesson gives a fixed script and a table of the common state shapes. Backtracking rounds test whether you can write the template without bugs (copy the solution, undo the choice) and bound its cost.

The same tables run inside ML. The word error rate (WER) of a speech model is an edit distance. The CTC loss of speech recognition and the forward and Viterbi algorithms of hidden Markov models are DP over (time step, state). Dynamic time warping aligns time series with an edit-distance-like table. The Bellman equation of reinforcement learning is a DP recurrence. Beam search in language model decoding is a pruned search over a tree of partial outputs.

Notation. $n$ is the input size (number of items or length of a string); $m$ and $n$ are the lengths of two strings; $A$ is an amount or a budget.

1. Predict first #

2. The picture #

Backtracking walks a tree of partial solutions #

Each node of the tree is a partial solution, each edge is one choice, and each leaf is a complete candidate. The simplest case is the subsets of $\{1, 2\}$: at depth $k$ you skip or take item $k+1$.

                 []
       skip 1 /      \ take 1
            []        [1]
   skip 2 /   \      /   \ take 2
        []    [2]  [1]   [1, 2]        4 leaves = 2^2 subsets

The recursion is a depth-first search of this tree (lesson 03). One list cur holds the current path. You choose (append), explore (recurse), then undo (pop), so that cur is correct for the next choice. Pruning cuts a subtree as soon as its partial solution cannot be completed. For the 8-queens problem (place 8 queens on a chessboard so that no two attack each other), placing one queen per row and skipping attacked squares visits 2,057 nodes, against $8^8 \approx 1.7 \cdot 10^7$ complete boards without pruning.

Dynamic programming merges equal nodes #

The recursion tree of fib(5), written f(5):

                    f(5)
              /             \
          f(4)               f(3)          f(3) appears 2 times,
        /      \            /    \         f(2) 3 times, f(1) 5 times:
     f(3)      f(2)       f(2)   f(1)      15 calls for 6 different values
    /    \     /  \       /  \
  f(2)  f(1) f(1) f(0)  f(1) f(0)
  /  \
f(1) f(0)

The value of f(3) does not depend on the path that led to it, so you can compute it once and reuse it. If you merge equal nodes, 6 states remain, and each $f(k)$ with $k \ge 2$ points to $f(k-1)$ and $f(k-2)$: a small DAG of states (directed acyclic graph, lesson 03).

So ask: does the answer below a node depend only on a small description of where you are (the state), or on the whole path? A small state that repeats calls for DP. If you must output every path, or the state is the whole path, use backtracking.

def subsets(nums):
    out, cur = [], []
    def go(i):
        if i == len(nums):
            out.append(cur)
            return
        go(i + 1)                 # skip nums[i]
        cur.append(nums[i]); go(i + 1); cur.pop()   # take nums[i]
    go(0)
    return out

3. Definitions and main results #

Backtracking #

go(state):
    if state is complete:  record a COPY of it; return
    for each choice allowed in state:
        if the choice can still lead to a solution:      # pruning
            apply the choice;  go(new state);  undo the choice

Three shapes cover most problems. They differ in how they avoid listing the same solution twice:

The cost of backtracking is (number of nodes) × (work per node), plus the cost of copying each solution. The next lemma shows that, for permutations, the inner nodes cost only a constant factor more than the leaves.

Lemma (size of the permutation tree). The tree of all permutations of $n$ items has $\sum_{k=0}^{n} \frac{n!}{(n-k)!} < e \cdot n!$ nodes.

Proof.

1. A node at depth $k$ is an ordered choice of $k$ different items out of $n$. There are $n (n-1) \cdots (n-k+1) = \frac{n!}{(n-k)!}$ of them.
2. Sum over $k$ and write $j = n - k$: $\sum_{j=0}^{n} \frac{n!}{j!} = n! \sum_{j=0}^{n} \frac{1}{j!} < e \cdot n!$, because $\sum_{j \ge 0} 1/j! = e$. $\blacksquare$

Each node scans $n$ candidates and each leaf copies $n$ items, so the total is $O(n \cdot n!)$.

Pruning comes in three kinds: feasibility (a constraint is already broken: two queens attack each other); order (sort the candidates and break at the first one that is too large, as in "Combination Sum"); bound (the partial cost is already worse than the best solution so far: branch and bound). With repeated input values, sort the input, and at each level skip a candidate equal to the previous one (i > start and nums[i] == nums[i-1]).

When dynamic programming applies #

DP applies when a problem has two properties:

• optimal substructure: an optimal solution is built from optimal solutions of smaller problems of the same form (for counting: the count is a sum of smaller counts);
• overlapping subproblems: a plain recursion meets the same smaller problem many times.

The DP script. Say these four things before you code:

1. State: what dp[i] (or dp[i][j]) means, in one sentence.
2. Recurrence: how dp[i] follows from smaller states, and why its cases cover every possible last choice.
3. Base cases and order: the smallest states, and a loop order in which every state comes after the states it needs.
4. Answer and cost: where the answer is (dp[n], or max(dp)), and the cost = number of states × work per state. Then ask: can I keep only the last row?

Memoization is the recursion plus a cache: before computing a state, look it up; after computing it, store it.

Theorem 1 (cost of memoization). If a recursion reaches $S$ different states, and each state does at most $W$ work and makes at most $W$ calls, then with a memo it costs $O(S \cdot W)$ time and $O(S)$ memory, plus the recursion depth.

Proof.

1. The body runs at most once per state; every later call returns the stored value in $O(1)$ (a hash lookup).
2. So the bodies cost at most $S \cdot W$ in total, the calls they make cost at most $S \cdot W$ lookups, and the memo holds $S$ values. $\blacksquare$

So the state must be small: its number of possible values is the cost.

From recursion to table to one row #

Top-down is the recurrence plus @functools.cache. It is a good first draft and computes only reachable states, but Python stops at a recursion depth of about 1,000. Bottom-up fills a table in a topological order of the DAG of states: no depth limit, and often you can keep only the last row or the last two values. Four classic 1-D examples:

The first two only look back 1 or 2 steps, so two variables replace the table: $O(1)$ memory.

State shapes #

The amount row is pseudo-polynomial: polynomial in the value $A$, but exponential in its number of bits. (Subset sum is NP-hard; the table is fast only for small amounts.)

Loop order changes the meaning. With a 1-D array over capacities $c$ and an item of weight $w$: for items used at most once (0/1 knapsack), loop over $c$ downwards, so that dp[c - w] still holds the value without this item; for unlimited items, loop upwards. When you count the ways to make an amount, coins in the outer loop count combinations (each multiset once, because coins are added in a fixed order), and amounts in the outer loop count sequences ($1{+}2$ and $2{+}1$ are then two ways).

Proving a recurrence: edit distance #

The edit distance (Levenshtein distance) between strings $a$ and $b$ is the smallest number of insertions, deletions and substitutions of single letters that turn $a$ into $b$. Write $a_i$ for the $i$-th letter (counting from 1), $m$ and $n$ for the lengths, and $D(i, j)$ for the edit distance between the first $i$ letters of $a$ and the first $j$ letters of $b$.

Picture an edit as an alignment: $a$ above $b$, with gaps - so that both rows have the same length and no column has two gaps. A column $(x, y)$ costs 0 if $x = y$ and 1 otherwise; a column $(a_i, -)$ is a deletion and $(-, b_j)$ an insertion. The cheapest alignment costs exactly the edit distance (Wagner and Fischer, 1974).

s t o p -
- t o p s        cost: 1 (delete s) + 0 + 0 + 0 + 1 (insert s) = 2

Theorem 2 (edit-distance recurrence). $D(i, 0) = i$, $D(0, j) = j$, and for $i, j \ge 1$

where $[a_i \ne b_j]$ is 1 if the letters differ and 0 if they are equal.

Proof.

1. Base cases. Aligning $i$ letters with the empty string needs $i$ columns $(a_k, -)$: cost $i$. In the same way $D(0, j) = j$.
2. Case analysis on the last column. An alignment of the two prefixes ends with $(a_i, -)$, with $(-, b_j)$ or with $(a_i, b_j)$. There is no other case: the last column contains $a_i$, or $b_j$, or both.
3. Cut and paste. Remove the last column. The rest aligns the prefixes of lengths $(i-1, j)$, $(i, j-1)$ or $(i-1, j-1)$. In an optimal alignment the rest is optimal too: if a cheaper rest existed, putting the same last column after it would give a cheaper alignment.
4. So the optimal cost is the cost of the last column plus $D$ of the remaining prefixes, for the best of the three cases. Each case can be realized, so the minimum is reached. $\blacksquare$

The same case analysis on the last column gives the recurrence of the longest common subsequence (LCS): $L(i, j) = L(i-1, j-1) + 1$ if $a_i = b_j$, otherwise $\max(L(i-1, j), L(i, j-1))$.

Recovering the solution (traceback). The table stores costs, not choices. To get the edits, walk back from $(m, n)$: at each cell, move to a neighbour (up, left or diagonal) that gives the minimum in the recurrence, and record the edit of that move. Keeping only two rows saves memory but loses this path; Hirschberg's algorithm (1975) recovers it in $O(mn)$ time and linear memory.

DP is a shortest path in a DAG. Make one node per cell $(i, j)$. A step down is a deletion (cost 1), a step right an insertion (cost 1), a diagonal step a match (0) or a substitution (1). $D(m, n)$ is the shortest path from $(0, 0)$ to $(m, n)$ in this edit graph, and the row-by-row fill is the "relax in topological order" algorithm of lesson 03.

Greedy or DP? #

A greedy algorithm makes the locally best choice and never revisits it (lesson 02). It is correct only when an exchange argument shows that the greedy choice is part of some optimal solution. For coins it fails in general: with coins $\{1, 3, 4\}$ and amount 6, greedy takes the largest coin first, $4 + 1 + 1$ (3 coins), but $3 + 3$ uses 2. Greedy works for "canonical" coin systems such as $\{1, 2, 5, 10\}$, but an interviewer expects the DP unless you can prove the greedy choice. A counterexample is the fastest way to say "greedy fails".

Longest increasing subsequence #

A subsequence keeps some items in their original order (not necessarily next to each other). The longest increasing subsequence (LIS) is the longest one whose values strictly increase. The state "$\text{end}[i]$ = length of the LIS that ends at item $i$" gives $\text{end}[i] = 1 + \max\{\text{end}[j] : j < i,\ x_j < x_i\}$ (or 1), and the answer is $\max_i \text{end}[i]$: $O(n^2)$ time.

A different state is faster. After reading a prefix of the input, let $\text{tails}[k]$ be the smallest last value of a strictly increasing subsequence of length $k + 1$. The LIS length is the length of tails.

Lemma (the tails array). tails is strictly increasing. A new value $x$ changes only the first position $k$ with $\text{tails}[k] \ge x$ (found with bisect_left): it sets $\text{tails}[k] = x$, or appends $x$ if there is no such $k$.

One binary search per value gives $O(n \log n)$. bisect_left gives the strictly increasing version; bisect_right gives the non-decreasing one. Note that tails is in general not a subsequence of the input: for $[3, 4, 1]$ it ends as $[1, 4]$.

Input size tells you the allowed cost #

A rough guide for Python, which does about $10^7$ simple steps per second:

Answers to section 1. (1) The plain recursion makes $C(n) = 1 + C(n-1) + C(n-2)$ calls with $C(0) = C(1) = 1$, so $C(n) = 2F(n+1) - 1$. For $n = 40$: $2 \cdot 165{,}580{,}141 - 1 = 331{,}160{,}281 \approx 3 \cdot 10^8$ calls. With a memo there are 41 states; each of the 39 states with $n \ge 2$ makes its 2 calls once, plus the first call: 79 calls (Theorem 1). (2) Listing: no. Every leaf is a different subset, and the output alone holds $n \, 2^{n-1}$ numbers; a memo cannot make the output shorter. Deciding the split: yes. "Can the suffix from index $i$ be split?" has the same answer however you reached $i$, so there are only $n + 1$ states. Without a memo the recursion is exponential (try "aaa…ab" with the words "a", "aa", "aaa").

4. Worked example #

(a) Coin Change with the script. Coins $\{1, 3, 4\}$, amount 6, fewest coins.

1. State: $c[a]$ = the fewest coins that make the amount $a$.
2. Recurrence: the last coin is 1, 3 or 4, so $c[a] = 1 + \min(c[a-1], c[a-3], c[a-4])$, using only the coins $\le a$. These three cases cover every possible last coin.
3. Base cases and order: $c[0] = 0$. Fill $a = 1, 2, \dots, 6$ upwards: each $c[a]$ needs only smaller amounts.
4. Answer and cost: $c[6]$; $7$ states × 3 coins = $O(A \cdot k)$.

So $c[6] = 2$, reached from coin 3 at $a = 6$, then coin 3 at $a = 3$: the coins are $3 + 3$. Greedy gives $4 + 1 + 1$, 3 coins.

(b) Edit distance from stop to tops, with the script.

1. State: $D(i, j)$ = edit distance between the first $i$ letters of stop and the first $j$ letters of tops.
2. Recurrence: Theorem 2.
3. Base cases and order: row 0 and column 0 are $0, 1, 2, 3, 4$. Fill row by row, left to right: each cell needs the cells above, to the left, and up-left.
4. Answer and cost: $D(4, 4)$; $5 \times 5 = 25$ cells of $O(1)$ work.

Three cells in detail:

• $(1, 1)$, s against t, different letters: $\min(D(0,1) + 1,\ D(1,0) + 1,\ D(0,0) + 1) = \min(2, 2, 1) = 1$ (substitute).
• $(1, 4)$, s against s, equal letters: $\min(D(0,4) + 1,\ D(1,3) + 1,\ D(0,3) + 0) = \min(5, 4, 3) = 3$.
• $(2, 1)$, t against t, equal letters: $\min(D(1,1) + 1,\ D(2,0) + 1,\ D(1,0) + 0) = \min(2, 3, 1) = 1$.

So the distance is $D(4, 4) = 2$. Traceback from $(4, 4)$, p against s: the left cell gives the minimum, $D(4, 3) + 1 = 2$, so the last edit is "insert s". At $(4, 3)$, $(3, 2)$ and $(2, 1)$ the letters are equal (p, o, t) and the diagonal gives the minimum: three matches. At $(1, 0)$ we are in column 0: "delete s". The alignment is the one drawn above Theorem 2. Substitutions alone (the Hamming distance) would cost 4; insertions and deletions let the alignment shift by one place.

5. In code #

Standard-library Python. The code counts the nodes of the 8-queens search, compares the plain and the memoized recursion, and checks both worked examples.

from functools import cache
import math


# 1) Backtracking with pruning: n queens, one queen per row.
def n_queens(n):
    cols, diag1, diag2 = set(), set(), set()   # attacked columns and diagonals
    solutions, nodes = 0, 0

    def go(row):
        nonlocal solutions, nodes
        nodes += 1                             # a node of the recursion tree
        if row == n:
            solutions += 1
            return
        for c in range(n):
            if c in cols or row - c in diag1 or row + c in diag2:
                continue                       # prune: this square is attacked
            cols.add(c); diag1.add(row - c); diag2.add(row + c)        # choose
            go(row + 1)                                                # explore
            cols.remove(c); diag1.remove(row - c); diag2.remove(row + c)  # undo

    go(0)
    return solutions, nodes


print(n_queens(4), n_queens(8), 8 ** 8)        # (2, 17) (92, 2057) 16777216


# 2) The same recursion with and without a memo: count how often the body runs.
def fib_runs(n, memo):
    runs = 0

    def f(k):
        nonlocal runs
        runs += 1
        return k if k < 2 else f(k - 1) + f(k - 2)

    if memo:
        f = cache(f)                           # the inner calls now go through the cache
    return f(n), runs


print(fib_runs(25, memo=False), fib_runs(25, memo=True))   # (75025, 242785) (75025, 26)


# 3) Coin change (fewest coins), bottom-up, and the greedy answer.
def coin_change(coins, amount):
    best = [0] + [math.inf] * amount           # best[a] = fewest coins for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] < math.inf else -1, best


def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):      # largest coin first
        count += amount // c
        amount %= c
    return count if amount == 0 else -1


print(coin_change([1, 3, 4], 6))               # (2, [0, 1, 2, 1, 1, 2, 2])
print(greedy_coins([1, 3, 4], 6))              # 3  (4 + 1 + 1), but 3 + 3 uses 2 coins


# 4) Edit distance: the full table of the worked example.
def edit_table(a, b):
    m, n = len(a), len(b)
    D = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        D[i][0] = i                            # delete i letters
    for j in range(n + 1):
        D[0][j] = j                            # insert j letters
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            D[i][j] = min(D[i - 1][j] + 1,                        # delete a[i-1]
                          D[i][j - 1] + 1,                        # insert b[j-1]
                          D[i - 1][j - 1] + (a[i - 1] != b[j - 1]))  # match or substitute
    return D


for row in edit_table("stop", "tops"):
    print(row)
# [0, 1, 2, 3, 4]
# [1, 1, 2, 3, 3]
# [2, 1, 2, 3, 4]
# [3, 2, 1, 2, 3]
# [4, 3, 2, 1, 2]

$2F(26) - 1 = 2 \cdot 121{,}393 - 1 = 242{,}785$ runs without the memo against 26 with it. On long inputs (more than about 1,000 levels), the memoized version fails with RecursionError and the bottom-up table does not; this is why interviewers often ask for the table.

6. Where it shows up #

• Speech and sequences. The word error rate (WER) is a word-level edit distance divided by the number of reference words. The CTC loss (Graves et al., 2006) sums over all alignments with a DP over (time step, position in the label). The forward algorithm of a hidden Markov model sums over paths and Viterbi takes the maximum, on the same (time, state) table.
• Reinforcement learning. The Bellman optimality equation $V(s) = \max_a \big(r(s, a) + \gamma\, \mathbb{E}[V(s')]\big)$ (value $V$, state $s$, action $a$, reward $r$, discount $\gamma$, next state $s'$) is a DP recurrence over states; value iteration fills its table. See the reinforcement learning track.
• Decoding. Beam search keeps the best $k$ partial outputs at each step: a backtracking search with aggressive pruning, so it can miss the most likely sequence.
• ML for science. DNA and protein alignment (Needleman–Wunsch, 1970; Smith–Waterman, 1981) is the edit-distance table with a substitution score matrix and gap penalties. Dynamic time warping (DTW) aligns two time series that run at different speeds: $D(i, j) = |x_i - y_j| + \min\big(D(i-1, j), D(i, j-1), D(i-1, j-1)\big)$.
• Solvers. SAT solvers descend from DPLL (1962), a backtracking search with pruning; mixed-integer programming solvers use branch and bound.

7. Common mistakes #

• Recording cur instead of a copy (cur[:]): all stored lists are one object, empty at the end.
• Forgetting to undo a choice (pop, used[i] = False): the state leaks into the next branch.
• Duplicates by order: a loop from 0 instead of from the start index gives $[2, 3]$ and $[3, 2]$ as two combinations.
• A state that misses information (on a circular street: was the first house robbed?): the memo then returns wrong values.
• Wrong base case or answer cell. Counting: ways[0] = 1 (one way to make nothing). Minimum: unreachable is $\infty$, and a final $\infty$ becomes what the task asks (often -1). "Ends at $i$": the answer is max(dp), not dp[-1].
• Wrong loop order (combinations or sequences; capacity downwards for 0/1 items).
• Assuming greedy works without a proof or a quick search for a counterexample.
• Python: @cache needs hashable arguments (indices, not lists); large inputs need the table because of the recursion limit.

8. Check yourself #

1. How many nodes does the permutation tree have for $n = 4$? Compare with $e \cdot 4!$.
   Answer

   $1 + 4 + 12 + 24 + 24 = 65$, and $e \cdot 24 \approx 65.2$. In fact the count is $\lfloor e \cdot n! \rfloor$ for every $n \ge 1$.
2. Coins $\{1, 2\}$, amount 4. How many combinations and how many sequences? Which loop nesting counts which?
   Answer

   3 combinations ($1{+}1{+}1{+}1$, $1{+}1{+}2$, $2{+}2$) and 5 sequences ($1111$, $112$, $121$, $211$, $22$). Coins in the outer loop count combinations; amounts in the outer loop count sequences.
3. Give the LCS length and the edit distance of stop and tops. Why is the edit distance never more than $m + n - 2L$, where $L$ is the LCS length?
   Answer

   $L = 3$ (top) and the edit distance is 2. A common subsequence of length $L$ gives an edit script: delete the other $m - L$ letters of $a$ and insert the other $n - L$ letters of $b$. So the distance is at most $m + n - 2L$; here $4 + 4 - 6 = 2$, and the bound is reached.
4. Run the tails method on $[3, 1, 4, 1, 5, 9, 2, 6]$. Give tails after each step and the LIS length. Is the final tails a subsequence of the input?
   Answer

   $[3] \to [1] \to [1, 4] \to [1, 4] \to [1, 4, 5] \to [1, 4, 5, 9] \to [1, 2, 5, 9] \to [1, 2, 5, 6]$. Length 4, for example $1, 4, 5, 9$. The final tails is not a subsequence: the 2 comes after the 5 in the input.
5. "Count the subsets of $\{1, \dots, 20\}$ with sum 50" and "list them". Which method for each, and at what cost?
   Answer

   Count with DP over the sum: ways[s], one downward loop over $s$ per item, $O(n \cdot S)$, here $20 \cdot 51$ updates; the count is 1,969. List with backtracking (take or skip, prune when the sum passes 50): at least the size of the output, 1,969 subsets times their length.
6. Longest palindromic subsequence of a string $s$: give the state, the recurrence, the base cases, the order and the cost.
   Answer

   $P(i, j)$ = length of the longest palindromic subsequence of $s_i \dots s_j$. If $s_i = s_j$: $P(i, j) = P(i+1, j-1) + 2$; otherwise $\max(P(i+1, j), P(i, j-1))$. Base: $P(i, i) = 1$ and $P(i+1, i) = 0$ (empty). Order: $i$ from $n - 1$ down to 0, $j$ from $i + 1$ up (shorter pieces first). Answer $P(0, n-1)$; $O(n^2)$ time, $O(n)$ memory with two rows. Example: bbbab gives 4. It also equals the LCS of $s$ and its reverse.

9. Interview angle #

Recognize the pattern from the wording:

The routine to say aloud. Brute-force recursion first ("try every last choice"). Then: "the same arguments come back, and the answer depends only on these arguments", so name the state. Say the script (state, recurrence, base cases and order, answer and cost). Write the memo version (the recurrence as code). Convert to a table if the depth can exceed 1,000, and keep fewer rows if memory matters. Test on the smallest inputs: empty string, amount 0, one item.

Typical questions and short model answers.

• "What is the difference between memoization and tabulation?" — Both compute each state once. Memoization is top-down: the recursion with a cache; it is quick to write and computes only the states it reaches, but it uses the call stack, so Python fails beyond about 1,000 levels. Tabulation is bottom-up: I fill the table in an order where every state comes after the states it needs. It has no recursion limit and lets me keep only the last row. The cost is the same: number of states × work per state.
• "Why is your recurrence correct?" (edit distance) — I look at the last column of an optimal alignment. It deletes $a_i$, inserts $b_j$, or pairs them, at cost 0 or 1. There is no other case. The rest of the alignment must be optimal for the shorter prefixes, otherwise I could replace it and get a cheaper whole. So the answer is the minimum over the three cases.
• "Can you do it in less memory?" — Each row needs only the previous row, so two rows, $O(n)$. For 1-D problems that look back a fixed number of steps (stairs, robber), two variables, $O(1)$. To also return the edits with linear memory, Hirschberg's divide and conquer.
• "Why not greedy?" — I give a counterexample: coins $\{1, 3, 4\}$, amount 6; greedy uses 3 coins, the optimum 2.
• "What is the complexity of generating all permutations?" — The tree has fewer than $e \cdot n!$ nodes, each scanning $n$ candidates, and each of the $n!$ leaves copies $n$ items: $O(n \cdot n!)$. This is optimal up to a constant, because the output itself has $n \cdot n!$ numbers.

Typical follow-ups. Return one optimal solution (traceback, or store the choice per state). Duplicates in the input (sort, skip equal siblings). Count instead of list (backtracking becomes DP). Circular input (House Robber II: run twice, without the first or without the last house). Very large amount (pseudo-polynomial: the table is too big; ask about constraints).

10. Practice #

The notebook for this lesson runs in Colab. Each exercise has a check cell that compares your code with a brute force on random inputs, and a folded solution:

1. subsets(nums): backtracking; checked against itertools.combinations and the count $2^n$.
2. coin_change(coins, amount): fewest coins or -1; checked against a BFS over amounts.
3. word_break(s, words): DP over prefixes; checked against a brute-force recursion.
4. edit_distance(a, b): the table plus a traceback that returns an alignment; the check verifies the cost and that the alignment is valid.
5. lis_tails(nums): the $O(n \log n)$ method; checked against the $O(n^2)$ DP on random arrays.

Timed practice (25 minutes each, talking aloud): Subsets II, Permutations, Combination Sum, N-Queens, House Robber II, Coin Change II, Longest Common Subsequence, Edit Distance, Partition Equal Subset Sum, Longest Increasing Subsequence.

Say it aloud (2 minutes, no notes): the DP script for Coin Change, then the proof of the edit-distance recurrence by case analysis on the last column.

11. Watch and read #

• Jeff Erickson, Algorithms, free PDF: ch. 2 (backtracking: n queens, subset sum, the general pattern), ch. 3 (dynamic programming: Fibonacci, memoization, longest increasing subsequence, edit distance, "greed is stupid"), §6.4 (dynamic programming as depth-first search in a DAG).
• cp-algorithms, Longest increasing subsequence: the $O(n^2)$ DP, the $O(n \log n)$ method with binary search, and how to restore the subsequence.
• MIT 6.006 Spring 2020, lecture notes and recitations (the course of the first two videos; recitations 15–17 have many solved DP problems).
• Problem lists: Grind 75 (topics Recursion, Dynamic Programming) and NeetCode 150 (sections Backtracking, 1-D Dynamic Programming, 2-D Dynamic Programming).