Edit Distance (Levenshtein) in Python: Measuring How Different Two Strings Are

Two strings are either equal or they are not. That is all == will ever tell you. Edit distance replaces that yes/no with a number: how many single-character changes it takes to turn one string into the other. "broke" and "bakes" are three changes apart. "receive" and "recieve" are two. That single number is what lets a search box forgive a typo, a spell-checker rank its suggestions, and a genome aligner say two sequences are related.

The version almost everyone means by "edit distance" is the Levenshtein distance, named after Vladimir Levenshtein, who defined it in 1965. It allows exactly three moves, each costing 1: insert a character, delete a character, or substitute one character for another. The distance is the smallest number of those moves that gets you from the source string to the target string.

Computing it is the cleanest two-dimensional dynamic programming problem there is: a three-line recurrence, a rectangle you fill left to right and top to bottom, and the answer in the bottom-right corner. What follows derives that recurrence rather than handing it over, fills the table by hand for a five-letter example, and recovers the actual list of edits by walking the table backwards.

The idea

Start with what the answer looks like. Line the two strings up against each other, column by column, allowing gaps:

Six columns. Three are free — b, k and e appear in both strings in the same relative order. Three cost 1 each: delete the r, replace the o with an a, insert the s. Total 3, and no alignment of these two words does better. That is the edit distance.

So the real problem is: out of all the ways to line two strings up, find the cheapest. There are exponentially many alignments, so you cannot enumerate them. Dynamic programming works because of one observation about the last column of the winning alignment. It has to be one of exactly four things:

• A match — the last characters are equal. Free, and what remains is the distance between the two strings with their last characters chopped off.
• A substitution — the last characters differ and are paired anyway. Cost 1, plus that same smaller distance.
• A deletion — the last source character is paired with a gap. Cost 1, plus the distance from the shortened source to the whole target.
• An insertion — the last target character is paired with a gap. Cost 1, plus the distance from the whole source to the shortened target.

Each case hands you a strictly smaller problem of the same shape, so take the cheapest. Write distance(i, j) for the distance between the first i characters of the source and the first j of the target:

• If source[i-1] and target[j-1] are equal, distance(i, j) = distance(i-1, j-1).
• Otherwise distance(i, j) = 1 + min(distance(i-1, j-1), distance(i-1, j), distance(i, j-1)) — substitute, delete, insert.

Plus the two base cases, which are the part people skip and then get wrong:

• distance(0, j) = j. The source prefix is empty, so you insert all j target characters.
• distance(i, 0) = i. The target prefix is empty, so you delete all i source characters.

A subproblem is nothing but a pair of prefix lengths, and there are only (n + 1) × (m + 1) of those. Compute each one once into a rectangle, where every cell reads three neighbours: diagonally up-left, directly above, directly to the left.

That picture is the entire algorithm. Everything below is bookkeeping.

Watching it work

Turn broke into bakes. Build a grid with one row per prefix of the source and one column per prefix of the target, empty prefixes included: six rows, six columns. The cell in row i, column j holds the distance between the first i letters of broke and the first j letters of bakes.

Fill the edges first, because they need no computation:

Row 0 is the distance from the empty string to b, ba, bak, bake, bakes — one insertion per character, so the cost is just the length: 0, 1, 2, 3, 4, 5. Column 0 is the same idea in reverse, b through broke deleted down to nothing one character at a time.

Now fill the interior row by row, left to right. Every cell only needs values that are already there.

Row b, column b. The characters match, so the cell copies the diagonal cell (0, 0), which holds 0. Correct: b and b are identical. Row b, column a differs, so it takes the cheapest of diagonal 0 + 1, above 1 + 1, and left 0 + 1, giving 1 — one insertion turns b into ba.

Row o, column a is the cell from the diagram above: source prefix bro, target prefix ba. The letters differ, so nothing is free. The diagonal, distance("br", "b") = 1, plus 1 for the substitution, is 2. Above, distance("br", "ba") = 1, plus 1 for deleting the o, is also 2. Left, distance("bro", "b") = 2, plus 1 for inserting the a, is 3. The cheapest is 2 — and note the genuine tie between substituting and deleting, because it matters later.

Carry on to the end:

The highlighted cells are where letters matched and the value came free off the diagonal: b against b, k against k, e against e. They run down-right in a staircase, and that staircase is the alignment from the first diagram. The bottom-right cell holds 3, the distance between the full strings, because row 5 means all of broke and column 5 means all of bakes.

The code

Start with the recurrence written out literally, with no table at all. It is worth seeing because it is the definition, and because it is a disaster.

RECURSIVE_CALLS = 0


def edit_distance_recursive(source: str, target: str) -> int:
    """Levenshtein distance by recursing on the last character of each string.

    Correct, and unusably slow: it re-solves the same pair of prefixes over
    and over. The counter exists only to make that blow-up visible.
    """
    global RECURSIVE_CALLS
    RECURSIVE_CALLS += 1

    if not source:
        return len(target)  # insert every remaining target character
    if not target:
        return len(source)  # delete every remaining source character

    if source[-1] == target[-1]:
        # Last characters agree, so that column of the alignment is free.
        return edit_distance_recursive(source[:-1], target[:-1])

    return 1 + min(
        edit_distance_recursive(source[:-1], target),       # delete source[-1]
        edit_distance_recursive(source, target[:-1]),       # insert target[-1]
        edit_distance_recursive(source[:-1], target[:-1]),  # substitute
    )


print("broke -> bakes:", edit_distance_recursive("broke", "bakes"))

RECURSIVE_CALLS = 0
print("kitten -> sitting:", edit_distance_recursive("kitten", "sitting"))
print("calls made:", RECURSIVE_CALLS)

RECURSIVE_CALLS = 0
print("abcdefgh -> stuvwxyz:", edit_distance_recursive("abcdefgh", "stuvwxyz"))
print("calls made:", RECURSIVE_CALLS)

broke -> bakes: 3
kitten -> sitting: 3
calls made: 3032
abcdefgh -> stuvwxyz: 8
calls made: 398593

Eight characters against eight characters with nothing in common costs nearly four hundred thousand calls, and there are only 81 distinct subproblems in that pair. Every one of them is being recomputed thousands of times.

The one-line fix is to remember answers. functools.cache (or functools.lru_cache(maxsize=None) before Python 3.9) turns the same function into a memoised one:

from functools import cache


@cache
def edit_distance_memo(source: str, target: str) -> int:
    """The same recursion, with every prefix pair solved at most once."""
    if not source:
        return len(target)
    if not target:
        return len(source)
    if source[-1] == target[-1]:
        return edit_distance_memo(source[:-1], target[:-1])
    return 1 + min(
        edit_distance_memo(source[:-1], target),
        edit_distance_memo(source, target[:-1]),
        edit_distance_memo(source[:-1], target[:-1]),
    )


print("kitten -> sitting:", edit_distance_memo("kitten", "sitting"))
stats = edit_distance_memo.cache_info()
print("distinct subproblems:", stats.misses, "- repeat calls served from cache:", stats.hits)

kitten -> sitting: 3
distinct subproblems: 50 - repeat calls served from cache: 48

Three thousand calls became 98, of which only 50 did any work. Those 50 are the table cells this particular recursion actually reaches; the bottom-up version below simply computes all 56 of them, which is cheaper than deciding which ones to skip.

Here is that bottom-up version — the one to actually use.

def edit_distance_table(source: str, target: str) -> list[list[int]]:
    """Build the full (len(source)+1) x (len(target)+1) distance table.

    table[i][j] is the edit distance between the first i characters of
    source and the first j characters of target.
    """
    rows, cols = len(source) + 1, len(target) + 1
    table = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        table[i][0] = i  # delete i characters to reach the empty string
    for j in range(cols):
        table[0][j] = j  # insert j characters to build target from nothing

    for i in range(1, rows):
        for j in range(1, cols):
            cost = 0 if source[i - 1] == target[j - 1] else 1
            table[i][j] = min(
                table[i - 1][j] + 1,         # delete source[i-1]
                table[i][j - 1] + 1,         # insert target[j-1]
                table[i - 1][j - 1] + cost,  # substitute, or free if equal
            )

    return table


def edit_distance(source: str, target: str) -> int:
    """Minimum insertions, deletions and substitutions turning source into target."""
    return edit_distance_table(source, target)[-1][-1]


def format_table(source: str, target: str) -> str:
    """Render the distance table the way the diagrams draw it."""
    table = edit_distance_table(source, target)
    header = "".join(f"{label:>4}" for label in ["-", *target])
    lines = ["    " + header]
    for label, row in zip(["-", *source], table):
        lines.append(f"{label:>4}" + "".join(f"{value:>4}" for value in row))
    return "\n".join(lines)


print(format_table("broke", "bakes"))
print("distance:", edit_distance("broke", "bakes"))
print("empty source:", edit_distance("", "bakes"))
print("identical:", edit_distance("bakes", "bakes"))

       -   b   a   k   e   s
   -   0   1   2   3   4   5
   b   1   0   1   2   3   4
   r   2   1   1   2   3   4
   o   3   2   2   2   3   4
   k   4   3   3   2   3   4
   e   5   4   4   3   2   3
distance: 3
empty source: 5
identical: 0

Those numbers are exactly the ones in the diagram above, which is the point of printing them: you can check the picture against the program.

How the code maps to the idea

The two initialisation loops are the base cases, and the only place the algorithm knows anything for free. table[i][0] = i is the deletion column, table[0][j] = j the insertion row. Set either to zero instead — a genuinely common bug — and the code will happily report that "broke" and "" are 0 apart.

The cost variable compresses the match/substitute distinction into one expression. When the characters agree, cost is 0 and the diagonal move is free; when they differ it is 1. There is no separate branch, because a match is just a substitution that happens to cost nothing.

The min of three is the four cases from the idea section: match and substitute are both diagonal moves, so they collapse into a single candidate once cost carries the difference.

The loop order is not arbitrary. Cell (i, j) reads (i-1, j), (i, j-1) and (i-1, j-1), so any order that finishes earlier rows before later ones, and earlier columns before later ones within a row, works. Row by row, left to right, does.

Edge cases fall out of the arithmetic. An empty source never enters the inner loop, and table[0][m] already holds m. Two identical strings walk the diagonal at zero cost. Wildly different lengths just make the table a long thin rectangle.

Recovering the actual edits

The number alone is often not what you want. A spell-checker wants to say which letter is wrong; a diff tool wants to show the change. The table already holds that information — walk backwards from the bottom-right corner, asking at each cell which neighbour it came from.

def edit_script(source: str, target: str) -> list[str]:
    """Walk the finished table backwards to recover one optimal list of edits."""
    table = edit_distance_table(source, target)
    i, j = len(source), len(target)
    steps: list[str] = []

    while i > 0 or j > 0:
        if (i > 0 and j > 0 and source[i - 1] == target[j - 1]
                and table[i][j] == table[i - 1][j - 1]):
            steps.append(f"keep      {source[i - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and table[i][j] == table[i - 1][j - 1] + 1:
            steps.append(f"replace   {source[i - 1]} -> {target[j - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and table[i][j] == table[i - 1][j] + 1:
            steps.append(f"delete    {source[i - 1]}")
            i -= 1
        else:
            steps.append(f"insert    {target[j - 1]}")
            j -= 1

    steps.reverse()
    return steps


for step in edit_script("broke", "bakes"):
    print(step)

keep      b
delete    r
replace   o -> a
keep      k
keep      e
insert    s

That is the alignment from the very first diagram, reconstructed from nothing but the numbers.

Two details deserve attention. The walk runs end to start, so steps comes out backwards and has to be reversed. And the branch order is the tie-breaking policy: match, then substitute, then delete, then insert. Remember the tie at row o, column a, where substituting and deleting both cost 2 — this code substitutes because that branch is tested first. Take the other and you get keep b, replace r -> a, delete o, keep k, keep e, insert s: a different script at the same cost of 3. Optimal edit scripts are frequently not unique and no policy is more correct than another, so choose one deliberately and your output will at least be stable.

Two rows instead of the whole table

Look at the recurrence again: cell (i, j) reads only from row i and row i-1. Everything above row i-1 is dead weight. So keep two rows, not n + 1 of them.

def edit_distance_two_rows(source: str, target: str) -> int:
    """Same numbers, but only two rows of the table are ever in memory."""
    # The distance is symmetric, so make target the shorter string; the rows
    # we keep are then min(n, m) + 1 long instead of max(n, m) + 1.
    if len(target) > len(source):
        source, target = target, source

    previous = list(range(len(target) + 1))

    for i, source_char in enumerate(source, start=1):
        current = [i] + [0] * len(target)
        for j, target_char in enumerate(target, start=1):
            cost = 0 if source_char == target_char else 1
            current[j] = min(
                previous[j] + 1,
                current[j - 1] + 1,
                previous[j - 1] + cost,
            )
        previous = current

    return previous[-1]


pairs = [("broke", "bakes"), ("kitten", "sitting"), ("", "abc"), ("same", "same"),
         ("a", "bbbbbbbbbb")]
for left, right in pairs:
    full = edit_distance(left, right)
    rolling = edit_distance_two_rows(left, right)
    print(f"{left!r:12} {right!r:12} full={full} two-row={rolling} agree={full == rolling}")

'broke'      'bakes'      full=3 two-row=3 agree=True
'kitten'     'sitting'    full=3 two-row=3 agree=True
''           'abc'        full=3 two-row=3 agree=True
'same'       'same'       full=0 two-row=0 agree=True
'a'          'bbbbbbbbbb' full=10 two-row=10 agree=True

The swap at the top is what turns O(max(n, m)) space into O(min(n, m)). Distance is symmetric — every insertion in one direction is a deletion in the other — so you are free to put the shorter string on the columns. A 12-character query against a 200,000-character document then needs 13 integers per row, not 200,001.

The price is that you can no longer backtrack: the path has been overwritten. Keep the whole table if you need the edit script, two rows if you only need the number.

Complexity

Time: O(n × m), where n and m are the two string lengths. The counting argument is short: the table has (n + 1) × (m + 1) cells, and filling one is a comparison, three additions and a three-way min — a fixed amount of work that does not depend on the string lengths. Constant work per cell times (n + 1)(m + 1) cells gives a total proportional to n × m.

The bound is the same in the best, average and worst case. There is no early exit and no lucky input: even two identical strings of length n fill all (n + 1)² cells, because the algorithm cannot know they are identical without looking. If you want a fast path for equal strings, test source == target first.

Space: O(n × m) for the full table, or O(min(n, m)) with the two-row version. The full table matters more than it sounds — two 20,000-character strings need 400 million Python integers, comfortably enough to exhaust memory. Reach for two rows unless you need the edit script.

The naive recursion is exponential. With no matching characters its call count satisfies T(i, j) = T(i-1, j) + T(i, j-1) + T(i-1, j-1) + 1, the recurrence behind the Delannoy numbers, which counts lattice paths from the corner down to the axes using down, left and diagonal steps. Those grow by a factor approaching 5.83 for each extra character added to both strings: 8 against 8 cost 398,593 calls above, and 9 against 9 costs about 2.2 million. The table version does 81 units of work on that input.

A table for deciding whether this is affordable at all:

Ten times the input is a hundred times the work. That quadratic wall is not a Python problem, and it is not fixable by trying harder: Backurs and Indyk proved in 2015 that no algorithm can compute edit distance in O(n^(2-e)) time for any positive e unless the Strong Exponential Time Hypothesis is false. Every practical speed-up below works by refusing to answer the general question.

Variants worth knowing

Damerau-Levenshtein adds a fourth move: swapping two adjacent characters costs 1 instead of 2. That matters enormously for typing errors, where form for from and teh for the are among the most common mistakes people make. The code below is the optimal string alignment variant, the one usually implemented; it adds one extra candidate to the min.

Normalised similarity turns the distance into a 0-to-1 score by dividing by the length of the longer string, which is the largest the distance can be. Distance 2 means something very different for two 4-character words than for two 40-character ones, so never compare raw distances across differently sized strings.

import difflib


def damerau_osa_distance(source: str, target: str) -> int:
    """Levenshtein plus one extra move: swapping two adjacent characters costs 1."""
    rows, cols = len(source) + 1, len(target) + 1
    table = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        table[i][0] = i
    for j in range(cols):
        table[0][j] = j

    for i in range(1, rows):
        for j in range(1, cols):
            cost = 0 if source[i - 1] == target[j - 1] else 1
            best = min(
                table[i - 1][j] + 1,
                table[i][j - 1] + 1,
                table[i - 1][j - 1] + cost,
            )
            # The last two characters are each other's neighbours, swapped.
            if (i > 1 and j > 1
                    and source[i - 1] == target[j - 2]
                    and source[i - 2] == target[j - 1]):
                best = min(best, table[i - 2][j - 2] + 1)
            table[i][j] = best

    return table[-1][-1]


def similarity(source: str, target: str) -> float:
    """1.0 for identical strings, 0.0 when every character has to change."""
    longest = max(len(source), len(target))
    if longest == 0:
        return 1.0
    return 1 - edit_distance(source, target) / longest


for left, right in [("form", "from"), ("cats", "acts"), ("broke", "bakes")]:
    print(f"{left:6} {right:6} levenshtein={edit_distance(left, right)} "
          f"damerau={damerau_osa_distance(left, right)} "
          f"similarity={similarity(left, right):.2f}")

print()
for candidate in ["receive", "relieve", "retrieve", "believe"]:
    print(f"recieve vs {candidate:9} levenshtein={edit_distance('recieve', candidate)} "
          f"damerau={damerau_osa_distance('recieve', candidate)}")

print()
print(f"difflib ratio broke/bakes: "
      f"{difflib.SequenceMatcher(None, 'broke', 'bakes').ratio():.2f}")
print("difflib close matches:", difflib.get_close_matches(
    "recieve", ["receive", "retrieve", "relieve", "believe"]))

form   from   levenshtein=2 damerau=1 similarity=0.50
cats   acts   levenshtein=2 damerau=1 similarity=0.50
broke  bakes  levenshtein=3 damerau=3 similarity=0.40

recieve vs receive   levenshtein=2 damerau=1
recieve vs relieve   levenshtein=1 damerau=1
recieve vs retrieve  levenshtein=2 damerau=2
recieve vs believe   levenshtein=2 damerau=2

difflib ratio broke/bakes: 0.60
difflib close matches: ['relieve', 'receive', 'retrieve']

The recieve block is the honest lesson there. Plain Levenshtein ranks relieve above receive, because one substitution beats two. Damerau pulls receive down to 1 by treating ie for ei as a single transposition — and now the two tie. Edit distance is a good filter and a poor ranker; real spell-checkers break these ties with word frequency, keyboard adjacency and phonetic keys layered on top of a distance cutoff.

Weighted costs come next. Make a substitution cost 2 and the algorithm stops substituting entirely, since a delete plus an insert also costs 2 — the result is the classic diff distance, which is the longest common subsequence problem in disguise. Give each character pair its own cost and you have Needleman-Wunsch, the global sequence alignment algorithm used in bioinformatics.

Capped distance is the variant you will actually need at scale. If you only care whether the distance is at most k, fill only a diagonal band of width 2k + 1, because any cell further from the diagonal than k already exceeds the cap. That is Ukkonen's algorithm, and it runs in O(k × min(n, m)) time.

What Python ships is not Levenshtein. difflib.SequenceMatcher uses a Ratcliff/Obershelp style match on the longest common contiguous blocks, and its ratio() is twice the matched length over the total length, not anything derived from an edit count. It is genuinely useful — get_close_matches is a fine fuzzy lookup for small lists and unified_diff powers plenty of tooling — but for a true Levenshtein number you write the twenty lines above or install a C extension such as rapidfuzz.

When to use it, and when not to

Use it when you are comparing short strings — names, words, product codes, addresses, sequence reads — and need a graded answer rather than equal/not equal. Under a few hundred characters per side the table is small and the code is boring, which is the ideal combination. Use it as a filter rather than a ranker: it is excellent at discarding everything more than two edits away and mediocre at ordering what remains.

Do not use it on long text. Two 50,000-character documents mean 2.5 billion cells, which is hours in Python. Compare documents at the level of lines or tokens instead of characters — that is what diff does, using longest common subsequence via Myers' algorithm on line hashes. difflib gives you this for free.

Do not scan a whole dictionary with it. Measuring a query against each of 300,000 words means 300,000 tables. Prune first: two strings whose lengths differ by more than k are automatically more than k apart, a free filter costing one subtraction. Then use a structure built for the job — a trie walked with one DP row per node prunes whole branches at once, a BK-tree exploits the triangle inequality, and Lucene compiles the query into a Levenshtein automaton.

Do not use it where order does not matter. To check whether two strings are anagrams or share a vocabulary, a character or token count is the right tool, and it is linear.

Where it shows up in the real world

PostgreSQL ships levenshtein() in its fuzzystrmatch extension, alongside levenshtein_less_equal() — the capped variant, which exists precisely because the uncapped one is too slow to run across a large table.

Apache Lucene, and so Elasticsearch and OpenSearch on top of it, implements fuzzy matching by compiling the query term into a Levenshtein automaton capped at an edit distance of 2. The cap is not laziness; it keeps the automaton small enough to intersect with the term dictionary quickly.

Git suggests corrections when you mistype a subcommand. That "did you mean" list comes from a Levenshtein implementation in levenshtein.c, with different weights per operation, so git comit finds commit.

Speech recognition and OCR are scored with edit distance and essentially nothing else. Word Error Rate is the substitutions plus deletions plus insertions needed to turn system output into the reference transcript, divided by the reference length — normalised Levenshtein distance over word tokens. Character Error Rate is the same measure over characters, and it is the standard for OCR post-correction work.

Bioinformatics uses the same table with a richer scoring scheme. Needleman-Wunsch global alignment is edit distance where each substitution has its own cost from a substitution matrix and gaps have their own penalty; Smith-Waterman is the local-alignment relative that finds the best-matching region instead of aligning end to end.

Spelling correction is the classic use. Peter Norvig's well-known 21-line corrector generates every string within edit distance 1 and 2 of the input and keeps those appearing in a word-frequency list — edit distance run backwards, enumerating instead of measuring.

Common mistakes

Initialising the base row and column to zero. The table starts as zeros, so forgetting the two initialisation loops does not crash — it silently reports that any string is 0 edits from the empty string. Always test against an empty input.

Off-by-one between table and string indices. Row i corresponds to source[i-1], not source[i], because row 0 is the empty prefix. Using source[i] gives an IndexError on the last row if you are lucky, and wrong answers if you are not.

Adding 1 on the diagonal when the characters match. This makes the algorithm report a nonzero distance between identical strings. If edit_distance(s, s) is not 0 for every s, this is the bug.

Mixing up which neighbour is which. The cell above is a deletion from the source, the cell to the left is an insertion from the target. Getting them backwards leaves the number correct, because the table is symmetric under swapping the strings, but the recovered edit script will be nonsense.

Backtracking after the two-row optimisation. The rows you needed have been overwritten. Either keep the full table or use Hirschberg's divide-and-conquer method, which recovers the alignment in O(min(n, m)) space at the cost of doubling the time.

Comparing raw distances across different lengths. A distance of 3 between two 5-letter words is a different world from a distance of 3 between two 50-letter ones. Normalise before you threshold.

Forgetting Unicode. len() counts code points, so an accented character written as a base letter plus a combining mark counts as two, and looks one edit away from the plain letter. Run both strings through unicodedata.normalize("NFC", text) before measuring, or your distances will depend on how the text was typed.

Practice

1. Add a max_distance parameter that abandons the computation and returns max_distance + 1 as soon as every value in the current row exceeds the cap.
2. Write a function returning the alignment as two equal-length strings padded with - for gaps, so broke and bakes print as two lines you can read down.
3. Change the substitution cost to 2 and confirm the result equals the number of deletions plus insertions an LCS-based diff would report.
4. Given a word list, find every word within distance 2 of a query, first by brute force and then with the length-difference filter, and count how many tables the filter avoids building.
5. Show that the optimal string alignment variant is not the true Damerau distance: the strings CA and ABC are 3 apart under the code above but 2 apart if you allow a transposition followed by an insertion between the swapped characters.

Summary

Edit distance is the two-dimensional dynamic programming problem to learn first, because the recurrence is genuinely derivable rather than memorised: look at the last column of the alignment, notice it can only be one of four things, and the rest follows. Fill a rectangle, read the corner, walk backwards if you want the edits themselves. The quadratic cost is real and unavoidable in general, so at scale you cap the distance, prune by length, or push the work into a trie or an automaton.

Write it once from the recurrence, keep the two-row version in your toolkit, and remember that the number is a filter rather than a verdict.

Keep reading

• Longest Common Subsequence — the same table with substitutions removed, and the algorithm behind diff.
• Dynamic Programming Explained — memoisation versus tabulation, and how to recognise a problem that has this shape.
• The 0/1 Knapsack Problem — the other classic two-dimensional table, where the axes are items and capacity.
• Big O Notation — why quadratic growth is the wall it is, worked through properly.