Dynamic programming

Dynamic programming solves problems that have two properties:

1. Optimal substructure — the best solution is built from the best solutions to subproblems.
2. Overlapping subproblems — the same subproblem turns up again and again.

Naive recursion recomputes the same thing exponentially many times. DP stores the partial results and goes from $O(2^n)$ to $O(n^2)$ or better.

Two ways of doing it:

• Memoisation (top-down): ordinary recursion plus a cache. The simplest — often @functools.cache is enough.
• Tabulation (bottom-up): fill a table in the right order. Faster and without recursion depth.

from functools import cache
import numpy as np

# 1. Edit distance (Levenshtein) — used for spelling correction and evaluation metrics
def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    d = np.zeros((m + 1, n + 1), dtype=int)
    d[:, 0] = np.arange(m + 1); d[0, :] = np.arange(n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i-1] == b[j-1] else 1
            d[i, j] = min(d[i-1, j] + 1,        # delete
                          d[i, j-1] + 1,        # insert
                          d[i-1, j-1] + cost)   # substitute
    return int(d[m, n])

print(edit_distance("kitten", "sitting"))   # 3

# 2. Viterbi — the most likely hidden sequence (POS tagging, speech recognition)
def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{s: start_p[s] * emit_p[s][obs[0]] for s in states}]
    path = {s: [s] for s in states}
    for t in range(1, len(obs)):
        V.append({}); new_path = {}
        for s in states:
            p, prev = max((V[t-1][f] * trans_p[f][s] * emit_p[s][obs[t]], f) for f in states)
            V[t][s] = p; new_path[s] = path[prev] + [s]
        path = new_path
    p, last = max((V[-1][s], s) for s in states)
    return path[last], p

# 3. Memoisation is often enough
@cache
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)
print(fib(100))    # immediately; without the cache: astronomical

Where you meet DP in ML: edit distance in evaluation metrics (WER for speech recognition), Viterbi in sequence labelling and HMMs, beam search as approximate DP, and the CTC loss in speech recognition.