Searching, sorting and dynamic programming

Memoization: remember what you've worked out

If someone asks you what 37 × 41 is, you work it out once. If they keep asking, you write the answer on a sticky note. Some recursive functions never learn this, and solve the same small problem again and again. The classic case is the Fibonacci numbers, where each number is the sum of the two before it:

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(25), "after", calls, "calls")

Hundreds of thousands of calls for one number! fib(23) gets worked out again and again. The fix is to save each answer the first time and look it up after. That's memoization, and Python gives you a decorator for it:

from functools import cache

calls = 0
@cache
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(25), "after", calls, "calls")
print(fib(200))

Each n is now computed once, so it's O(n) instead of growing exponentially.

calls = 0
seen = {}
def f(n):
    global calls
    if n in seen: return seen[n]
    calls += 1
    seen[n] = n * n
    return seen[n]
f(3); f(3); f(3)
print(calls)

Dynamic programming

Dynamic programming (DP) is memoization turned into a plan. You break a problem into small subproblems, solve them in an order where each one only needs answers you already have, and store those answers in a table. The name is old and unhelpful. Think of it as "fill in a table of smaller answers", the way a mileage chart lets you read off a long trip from shorter ones.

A famous example is edit distance: the fewest single-letter changes (insert, delete or swap a letter) that turn one word into another. Spell checkers use it to suggest "tent" when you type "tnet". Search engines use it to forgive typos, and diff tools use a close relative.

Build a table where cell [i][j] holds the distance between the first i letters of word A and the first j letters of word B:

• The first row and column are easy: turning "" into the first j letters takes j inserts.
• For any other cell, look at the letters A[i-1] and B[j-1]. If they match, the cell copies its diagonal neighbor [i-1][j-1], at no cost. Otherwise take 1 plus the smallest of three neighbors: left (insert), above (delete) and diagonal (swap).

The answer is the bottom-right cell.

In plain words: each cell asks "what's the cheapest way to get this far?", and answers using cells you've already filled in.

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

table = edit_table("tent", "tnet")
print("    ''  t  n  e  t")
for label, row in zip(["''", "t ", "e ", "n ", "t "], table):
    print(label, row)
print("distance:", table[-1][-1])

Use the library, understand the idea

You'll almost never write your own sort for real work. You don't build your own car to learn how engines work either, but knowing helps. Python's sorted is carefully built, well tested, and fast on the partly sorted data that real programs tend to have. Learning merge sort is worthwhile anyway, because it teaches the idea of dividing a problem and combining the answers, which comes up everywhere.

The same goes for binary search. Python has it in the bisect module. But you must know its one rule: the data has to be sorted. On unsorted data, it doesn't fail with an error. It gives wrong answers, and bugs like that are hard to find. A quick check while testing, assert items == sorted(items), is worth the line.

Recursion and dynamic programming, demystified

Recursion has a reputation for being slow, and the plain version can be. Computing Fibonacci numbers recursively redoes the same work billions of times. But once you add memoization, each answer is worked out only once, and it's as fast as a loop. Often the slowness was never about recursion, only about repeated work.

The name "dynamic programming" misleads nearly everyone. It has nothing to do with dynamic code. It's a name from the 1950s for a simple idea: break a problem into smaller ones that overlap, then fill in a table of their answers, starting with the smallest. If you can describe each answer in terms of smaller answers, you can write it down this way. You saw it in edit distance, and it's the method behind tools that compare two documents.