Dynamic programming guide · 6/6

Real-World Use

Many everyday tools run a DP inside, often under a different name. This chapter surveys them, shows two small examples and lists the mistakes that most often break DP code.

Where DP shows up

Diff and version control: comparing two files is an LCS / shortest edit script problem. GNU diff and Git's default diff use Myers' algorithm, which runs in O(ND) time for D differences.
Spell checking and fuzzy search: edit distance (Levenshtein) ranks candidate words by how many keystrokes separate them from the query.
Bioinformatics: Needleman-Wunsch (global) and Smith-Waterman (local) align DNA or protein sequences with a scored edit-distance table.
Speech, text and signals: the Viterbi algorithm finds the most likely hidden-state sequence in a hidden Markov model, for speech recognition, part-of-speech tagging and decoding convolutional codes.
Networking: distance-vector routing protocols such as RIP are built on the Bellman-Ford recurrence.
Databases: query planners choose join orders with DP over subsets of tables, an idea from IBM's System R. PostgreSQL switches from this search to its genetic optimizer (GEQO) when a query joins many tables.
Typesetting: TeX's Knuth-Plass line breaking picks break points for a whole paragraph by minimizing total "badness".
Planning: value iteration in reinforcement learning applies the Bellman equation; budgeting and cargo loading are knapsack variants.

Example: suggest the closest command

A CLI can suggest a fix for a mistyped command using edit distance with a rolling row.

def edit_distance(s: str, t: str) -> int:
    prev = list(range(len(t) + 1))
    for i, a in enumerate(s, start=1):
        cur = [i] + [0] * len(t)
        for j, b in enumerate(t, start=1):
            cur[j] = prev[j - 1] if a == b else 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]


def suggest(word: str, commands: list[str], max_distance: int = 2) -> str | None:
    best = min(commands, key=lambda c: edit_distance(word, c))
    return best if edit_distance(word, best) <= max_distance else None


print(suggest("stauts", ["status", "commit", "push", "stash"]))  # status
print(suggest("deploy", ["status", "commit", "push", "stash"]))  # None

Python's difflib.get_close_matches is similar, but it ranks by a SequenceMatcher similarity ratio, not minimal edit distance.

Example: Viterbi on a tiny model

A monitor sees responses as "fast" or "slow" and guesses whether the server was "ok" or "degraded" at each moment. Viterbi keeps, for each state at time t, the best path probability and a back pointer.

def viterbi(observations, states, start, trans, emit):
    best = [{s: (start[s] * emit[s][observations[0]], None) for s in states}]
    for obs in observations[1:]:
        prev = best[-1]
        best.append({
            s: max((prev[p][0] * trans[p][s] * emit[s][obs], p) for p in states)
            for s in states
        })
    state = max(states, key=lambda s: best[-1][s][0])
    path = [state]
    for layer in reversed(best[1:]):
        state = layer[state][1]
        path.append(state)
    return path[::-1]


states = ("ok", "degraded")
start = {"ok": 0.9, "degraded": 0.1}
trans = {"ok": {"ok": 0.95, "degraded": 0.05}, "degraded": {"ok": 0.2, "degraded": 0.8}}
emit = {"ok": {"fast": 0.9, "slow": 0.1}, "degraded": {"fast": 0.3, "slow": 0.7}}
print(viterbi(["fast", "fast", "slow", "slow", "slow", "fast"], states, start, trans, emit))
# ['ok', 'ok', 'degraded', 'degraded', 'degraded', 'degraded']

Real implementations add log probabilities, because long products of small numbers underflow to zero.

Common pitfalls

Wrong state: if the answer depends on something the state does not record (remaining capacity, previous choice), the cache returns answers for the wrong situation.
Loop direction: in the one-row 0/1 knapsack, iterating capacities upwards silently turns it into the unbounded knapsack.
Recursion depth: Python's default limit is about 1000 frames; long chains need a bottom-up loop.
Overflow: counts grow fast. Use 64-bit integers or a modulus in C++ and Java.
Unbounded caches: functools.cache never evicts, so a long-running service can grow without limit; use lru_cache(maxsize=...) or clear it.
Unhashable arguments: cached functions need hashable arguments, so pass tuples or strings instead of lists.

from functools import cache, lru_cache


@cache
def total(items: tuple[int, ...]) -> int:
    return sum(items)


try:
    total([1, 2, 3])
except TypeError as error:
    print("lists cannot be cache keys:", error)
print(total((1, 2, 3)))  # 6


@lru_cache(maxsize=1024)  # evicts least recently used entries
def score(word: str) -> int:
    return sum(map(ord, word))


score.cache_clear()  # or free everything explicitly

Summary

DP powers diff, spell checking, sequence alignment, speech decoding, routing, query planning and typesetting.
Production code adds log probabilities, bounded caches or rolling rows to the textbook recurrence.
Most DP bugs come from an incomplete state, a wrong loop direction, recursion limits or overflow.