Deleting the source character advances only the source bookmark. Inserting the target character advances only the target bookmark. Replacing consumes both. Matching consumes both without paying an edit.

dp[i][j] is the minimum cost to convert a[i:] into b[j:]. Empty-source conversion costs the number of remaining target characters; empty-target conversion costs the number of remaining source characters. If characters match, use dp[i+1][j+1]. Otherwise pay one plus the minimum of deletion, insertion, and replacement suffix costs. Reverse index order makes all three dependencies ready. Every first operation is considered, and each smaller answer is optimal by induction.

What the function promises: a and b are strings. Insertion, deletion, and replacement each cost one. Return minimum edit count, including empty-string cases.

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

assert edit_distance("cat", "cut") == 1
assert edit_distance("", "abc") == 3
assert edit_distance("horse", "ros") == 3
assert edit_distance("same", "same") == 0

Work and storage: O((m+1)(n+1)) time and space. If only the numeric distance is required, rolling rows can reduce storage; reconstructing an edit sequence needs retained choices or an additional reconstruction strategy.

When to recognize it: Two reading positions describe the remaining conversion. Each edit advances one or both positions.

Check before applying it: A common subsequence alone does not account for unit-cost replacement. The allowed operations determine the recurrence.

No. Give each branch its own cost: 1+delete, 1+insert, 3+replace. A delete-plus-insert may now beat replacement. State coordinates can stay the same while transition semantics change.