Dynamic Programming

1. Climbing Stairs Easy

Problem

You climb a staircase of n steps, taking either 1 or 2 steps at a time. How many distinct ways are there to reach the top?

The five questions

1. State: ways[i] is the number of distinct ways to reach step i.
2. Recurrence: the last move was either a 1 from step i - 1 or a 2 from step i - 2, and those two sets of routes are disjoint, so ways[i] = ways[i - 1] + ways[i - 2].
3. Base: ways[1] = 1, ways[2] = 2.
4. Order: increasing i.
5. Answer: ways[n].

That is the Fibonacci sequence, offset by one. Saying so immediately is a good start.

Solution

def climb_stairs(n: int) -> int:
    """Number of distinct ways to climb n steps taking 1 or 2 at a time.

    Args:
        n: Number of steps, n >= 1.

    Returns:
        The count of distinct climbs.

    Example:
        >>> climb_stairs(5)
        8
    """
    # Base cases: n = 1 has 1 way, n = 2 has 2 ways (1+1 or 2).
    # In both, the answer is n itself.
    if n <= 2:
        return n

    # Only the last two values are ever needed, so keep two variables
    # instead of an array. O(1) space.
    # Seeds: two_back = ways(1) = 1, one_back = ways(2) = 2.
    two_back, one_back = 1, 2

    # Each pass computes ways(step) for step 3..n. Start at 3: steps 1 and 2
    # are the seeds. n + 1 so that step n is included.
    # Invariant: two_back = ways(step - 2), one_back = ways(step - 1).
    for _ in range(3, n + 1):
        # Slide up one step. New count = sum of the two counts below it.
        two_back, one_back = one_back, two_back + one_back

    # After the last pass, one_back = ways(n).
    return one_back

The progression to show

from functools import cache


def climb_stairs_memo(n: int) -> int:
    """Step 1: the brute force, made linear by one decorator."""

    # @cache: each step is computed once, so n calls instead of about 2 ** n.
    @cache
    def ways(step: int) -> int:
        # Base: step 1 has 1 way, step 2 has 2 ways. Both equal step itself.
        if step <= 2:
            return step
        # Last move was a 1 (from step - 1) or a 2 (from step - 2). Add both.
        return ways(step - 1) + ways(step - 2)

    return ways(n)


def climb_stairs_table(n: int) -> int:
    """Step 2: same thing bottom-up, O(n) space."""
    # Same base as above: the answer is n for n = 1 or 2.
    if n <= 2:
        return n

    # (n + 1): +1 so index n exists. 0 is a placeholder. Slot 0 is never read.
    ways = [0] * (n + 1)
    # Base cases: 1 way to reach step 1, 2 ways to reach step 2.
    ways[1], ways[2] = 1, 2

    # Start at 3: steps 1 and 2 are base cases. n + 1 so that n is included.
    # Invariant: ways[1..i-1] are all final.
    for i in range(3, n + 1):
        # i - 1: last move was one step. i - 2: last move was two steps.
        ways[i] = ways[i - 1] + ways[i - 2]

    # Slot n is the top step.
    return ways[n]

Brute force to memoised to tabulated to two variables. Walking an interviewer through that chain in ninety seconds demonstrates the method, which is what the question is for.

Reading the figure. Grey slots are the base cases, 1 way and 2 ways. Each blue slot gets two arrows, one from i - 1 and one from i - 2. Their values add. The green slot is the answer, ways[5] = 8. The bottom row shows the O(1) version. Each pass shifts the pair right by one step, and the right box ends on 8.

Variations you should expect

Edge cases to raise

• n = 1 gives 1, n = 2 gives 2. Both handled by the guard.
• n = 0: arguably 1, the empty climb. The guard returns 0. Ask which is wanted; it is a fair question.
• Large n: Python integers grow without limit, so no overflow, but the numbers get long. Worth a sentence.

2. Coin Change Medium

Problem

Given coin denominations and a target amount, return the fewest coins that sum to exactly that amount, or -1 if it is impossible. You have unlimited coins of each denomination.

Why greedy fails

The five questions

1. State: best[v] is the fewest coins summing to exactly v.
2. Recurrence: the last coin used was some c ≤ v, so best[v] = 1 + min(best[v - c]) over all such c.
3. Base: best[0] = 0. Zero coins make zero.
4. Order: increasing v, so best[v - c] is always ready.
5. Answer: best[amount], or -1 if it is still the sentinel.

Solution

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins summing to exactly amount, or -1 if impossible.

    Args:
        coins: Distinct positive denominations, unlimited supply of each.
        amount: Target sum, amount >= 0.

    Returns:
        The minimum number of coins, or -1.

    Example:
        >>> coin_change([1, 3, 4], 6)
        2
    """
    # Any real answer uses at most `amount` coins (all of value 1), so
    # amount + 1 is unreachable and makes a clean finite sentinel.
    unreachable = amount + 1
    # (amount + 1): +1 so index amount exists, slots 0..amount.
    best = [unreachable] * (amount + 1)
    # Base case: 0 coins make amount 0.
    best[0] = 0

    # value is the amount being solved. Start at 1: slot 0 is the base case.
    # amount + 1 so that amount itself is included.
    # Invariant: best[0..value-1] are all final.
    for value in range(1, amount + 1):
        # Try each coin as the LAST coin used.
        for coin in coins:
            if coin <= value:            # coin fits, so value - coin >= 0
                # best[value - coin] coins for the rest, + 1 for this coin.
                best[value] = min(best[value], best[value - coin] + 1)

    # -1 is the required "impossible" answer when the sentinel never moved.
    return -1 if best[amount] == unreachable else best[amount]

Walkthrough

coins = [1, 3, 4], amount = 6:

The winner at v = 6 comes through the 3-coin, which is exactly the case greedy misses.

Reading the figure. Each circle is an amount still to pay. Each arrow spends one coin and moves left by its value. The red path is greedy, which always takes the biggest coin that fits. The green path is the DP answer. The numbers under the bottom line are best[v] from the table above. Notice that best[3] = 1. That is why the hop from 6 to 3 wins.

The sibling: counting combinations

def coin_change_ways(coins: list[int], amount: int) -> int:
    """Coin Change II: how many distinct combinations sum to amount."""
    # (amount + 1): +1 so index amount exists. 0: no ways found yet.
    ways = [0] * (amount + 1)
    ways[0] = 1                      # one way to make zero: take nothing

    # Coins on the OUTSIDE loop. This fixes an order on the coins, so
    # 1+3 and 3+1 are counted once. Swapping the loops counts permutations.
    # Invariant: after a coin's pass, ways[v] counts the combinations of the
    # coins seen so far that sum to v.
    for coin in coins:
        # Start at coin: smaller values cannot hold this coin.
        # amount + 1 so amount is included. Forwards, so a coin can repeat.
        for value in range(coin, amount + 1):
            # Each way to make value - coin, plus this coin, makes value.
            ways[value] += ways[value - coin]

    return ways[amount]

Edge cases to raise

• amount == 0: returns 0, from the base case.
• No combination works, such as coins = [2] with amount = 3: returns -1.
• A coin larger than the amount: skipped by the coin <= value guard.
• Empty coin list with a positive amount: returns -1.
• Using float("inf") instead of the sentinel also works, but then inf + 1 appears in the arithmetic. The finite sentinel avoids that entirely.

3. Longest Increasing Subsequence Medium

Problem

Return the length of the longest strictly increasing subsequence of an array. A subsequence may skip elements but must keep the original order.

The state that does not work, and the one that does

The five questions

1. State: best[i] = LIS length ending exactly at i.
2. Recurrence: best[i] = 1 + max(best[j]) over all j < i with nums[j] < nums[i].
3. Base: best[i] = 1. Every element alone is a subsequence of length one.
4. Order: increasing i.
5. Answer: max(best), not best[-1], because the best subsequence need not end at the last element.

Solution: O(n²)

def length_of_lis(nums: list[int]) -> int:
    """Length of the longest strictly increasing subsequence.

    Args:
        nums: Integers, in any order.

    Returns:
        The length of the longest strictly increasing subsequence.

    Example:
        >>> length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])
        4
    """
    # Empty input has no subsequence: length 0. Also guards max() below.
    if not nums:
        return 0

    # best[i] is the LIS length ending exactly at index i.
    # 1: every element alone is an increasing run of length 1.
    best = [1] * len(nums)

    # i is the end index. Start at 1: index 0 has nothing before it.
    # Invariant: best[0..i-1] are all final.
    for i in range(1, len(nums)):
        # j scans every earlier index. range(i) stops at i - 1.
        for j in range(i):
            if nums[j] < nums[i]:     # nums[i] can extend a run ending at j
                # + 1 for appending nums[i] to that run.
                best[i] = max(best[i], best[j] + 1)

    # The optimum can end anywhere, so take the maximum over all endings.
    return max(best)

Solution: O(n log n), patience sorting

import bisect


def length_of_lis_fast(nums: list[int]) -> int:
    """Same answer in O(n log n) by keeping the best tail for each length.

    tails[k] is the smallest possible final value of any increasing
    subsequence of length k + 1 seen so far. It is sorted by construction,
    so each element can be placed with a binary search.
    """
    # Empty: no lengths reached yet.
    tails: list[int] = []

    # Invariant: tails[k] is the smallest tail of any increasing run of
    # length k + 1 among the values seen so far, and tails is sorted.
    for value in nums:
        # bisect_left: first slot with tails[slot] >= value. Left, not right,
        # so an equal value replaces rather than extends (strictly increasing).
        index = bisect.bisect_left(tails, value)

        if index == len(tails):      # value beats every tail: slot is past the end
            tails.append(value)      # extends the longest run found so far
        else:
            tails[index] = value     # a smaller tail for that length: strictly better

    # One slot per length reached, so the count is the LIS length.
    return len(tails)

Walkthrough of the fast version

nums = [10, 9, 2, 5, 3, 7, 101, 18]:

Length 4. Notice [2, 3, 7, 18] happens to be a real subsequence here, but that is a coincidence, not a guarantee.

Reading the figure. Each column is the state after reading the bold value on top. The stack under it is tails, index 0 at the top. Amber marks the one slot that changed, found by bisect_left. Blue slots stay as they were. A value bigger than every tail appends and makes the stack taller. Any other value replaces a tail with a smaller one. The last column, in green, has height 4.

Edge cases to raise

• Empty array: 0. The max() in the DP version would raise on an empty list, hence the guard.
• Strictly decreasing input: answer 1.
• All equal: answer 1, because the requirement is strictly increasing.
• Non-decreasing allowed instead: switch bisect_left to bisect_right in the fast version, and < to <= in the DP. One-character changes, worth flagging.
• Reconstructing the actual subsequence needs a parent-pointer array; the fast version makes that noticeably harder. Mention it if asked.

4. 0/1 Knapsack Medium

Problem

Each item has a weight and a value. Choose a subset with total weight at most capacity that maximises total value. Each item may be taken at most once, which is the “0/1”.

The five questions

1. State: best[i][w] is the maximum value using only the first i items within weight budget w.
2. Recurrence: for item i there are exactly two options, skip it or take it:
   best[i][w] = max(best[i-1][w], best[i-1][w - weight[i]] + value[i]), the second only when it fits.
3. Base: best[0][w] = 0. No items, no value.
4. Order: items outer, capacities inner.
5. Answer: best[n][capacity].

Solution: 2D table

def knapsack_2d(weights: list[int], values: list[int], capacity: int) -> int:
    """Maximum value from a subset of items fitting inside capacity.

    Args:
        weights: Positive item weights.
        values: Item values, same length as weights.
        capacity: Maximum total weight, capacity >= 0.

    Returns:
        The best achievable total value.

    Raises:
        ValueError: If weights and values have different lengths.

    Example:
        >>> knapsack_2d([1, 3, 4, 5], [1, 4, 5, 7], 7)
        9
    """
    if len(weights) != len(values):
        raise ValueError("weights and values must have the same length")

    n = len(weights)
    # best[i][room]: max value from the first i items within budget room.
    # n + 1 rows: row 0 is "no items". capacity + 1 columns: rooms 0..capacity.
    # 0: no items, or no room, is worth 0.
    # A comprehension, NOT [[0] * m] * n, which aliases one row n times.
    best = [[0] * (capacity + 1) for _ in range(n + 1)]

    # i counts the items considered. Start at 1: row 0 is the base row.
    # n + 1 so that item n is included.
    # Invariant: row i - 1 is complete when the pass for i starts.
    for i in range(1, n + 1):
        # i - 1: item number i sits at list index i - 1.
        weight, value = weights[i - 1], values[i - 1]

        # room is every budget. capacity + 1 so capacity itself is included.
        for room in range(capacity + 1):
            # Skip item i: same value as the first i - 1 items in the same room.
            skip = best[i - 1][room]

            if weight <= room:         # item fits in this budget
                # Take it: best of the first i - 1 items in the leftover room.
                take = best[i - 1][room - weight] + value
                best[i][room] = max(skip, take)
            else:
                best[i][room] = skip    # too heavy, so skip is the only option

    # All n items considered, full budget.
    return best[n][capacity]

Solution: one row, and the direction that matters

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """Same answer in O(capacity) space.

    Row i depends only on row i - 1, so one array suffices. The inner loop
    must run BACKWARDS: it guarantees that best[room - weight] still holds
    the previous item's value, which is what enforces "each item at most once".
    """
    # best[room]: max value within budget room. +1 so room = capacity exists.
    # 0: before any item, every budget is worth 0.
    best = [0] * (capacity + 1)

    # Invariant: at the top of each pass, best is the row for the items
    # before this one.
    for weight, value in zip(weights, values):
        # Walk room down from capacity to weight. weight - 1 is the exclusive
        # stop, so weight is included. -1 step = backwards: each item used once.
        for room in range(capacity, weight - 1, -1):
            # Skip (keep best[room]) or take (previous item's best[room - weight],
            # plus this value).
            best[room] = max(best[room], best[room - weight] + value)

    # Full budget, every item considered.
    return best[capacity]

Walkthrough

weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7. The optimum takes items 2 and 3, weights 3 + 4 = 7 and values 4 + 5 = 9. Taking item 4 alone gives 7; items 1 and 4 give 1 + 7 = 8 at weight 6. So the answer is 9.

Reading the figure. Each cell is best[i][w]. A straight down arrow means skip, so the value copies from the row above. A slanted arrow means take, so it comes from w - weight columns to the left, plus the item’s value. Amber cells are the trace from the answer back to the base row. The red dashed arrow is the losing take of item 4, worth only 8.

The family this unlocks

Edge cases to raise

• capacity == 0: returns 0.
• No items: returns 0.
• An item heavier than the capacity: the range bound skips it entirely.
• Zero-weight items with positive value: always taken, and safe here. Worth confirming they can occur.
• To recover which items were chosen you need the full 2D table and a backward walk. The compressed version cannot reconstruct the set. Say so if the problem asks for the items.

5. Maximum Subarray (Kadane) Medium

Problem

Given an integer array that may contain negatives, return the largest sum of any non-empty contiguous subarray.

The five questions

1. State: ending[i] is the largest sum of a subarray that ends exactly at index i.
2. Recurrence: a subarray ending at i either extends the best one ending at i - 1 or starts fresh at i, so ending[i] = max(nums[i], ending[i - 1] + nums[i]).
3. Base: ending[0] = nums[0].
4. Order: increasing i.
5. Answer: max(ending), because the best subarray can end anywhere. Track it as you go.

Solution

def max_subarray_kadane(nums: list[int]) -> int:
    """Largest sum of any non-empty contiguous subarray (Kadane).

    Args:
        nums: Integers, may be negative, with at least one element.

    Returns:
        The maximum subarray sum.

    Raises:
        ValueError: If nums is empty.

    Example:
        >>> max_subarray_kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        6
        >>> max_subarray_kadane([-3, -1, -2])
        -1
    """
    # The answer must be a non-empty subarray, so an empty input has none.
    if not nums:
        raise ValueError("nums must be non-empty")

    # Two-variable state instead of a table:
    #   ending_here = best sum of a subarray that ENDS at the current index.
    #   best = best sum of any subarray seen so far.
    # nums[0]: index 0 is the first element. The only subarray ending there
    # is [nums[0]], so both variables start at it.
    ending_here = best = nums[0]

    # nums[1:]: start at index 1, because index 0 seeded both variables.
    # Invariant: ending_here is the best sum ending at the previous index,
    # and best is the best sum over every subarray seen so far.
    for value in nums[1:]:
        # Extend the run that ended one step back, or start fresh at value.
        # Fresh wins exactly when the old run is negative and only drags.
        ending_here = max(value, ending_here + value)
        # The best subarray can end anywhere, so keep a running maximum.
        best = max(best, ending_here)

    return best

Walkthrough

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

• Start: ending_here = best = -2.
• 1: fresh 1 beats -2 + 1. ending 1, best 1.
• -3: extend to -2. best stays 1.
• 4: fresh 4 beats -2 + 4. ending 4, best 4.
• -1, 2, 1: extend to 3, 5, 6. best 6.
• -5, 4: ending drops to 1, then 5. best stays 6, from [4, -1, 2, 1].

Reading the figure. Read the columns left to right. The middle row is ending_here. Amber marks a fresh start, where the number alone beats extending. That happens at 1 and at 4. Blue cells extend the run. The bottom row is best, the largest ending seen so far. It peaks at 6, in green, and never drops after that.

Edge cases to raise

• All negative, such as [-3, -1, -2]: the answer is the largest single element, -1. Seeding with 0 instead of nums[0] would wrongly return 0.
• Empty input: no non-empty subarray exists. Ask what to return. This version raises.
• Asked for the subarray itself: record the start index each time you start fresh, and the end index each time best improves.
• Maximum product subarray: track both the largest and the smallest product ending here, because a negative flips them.

6. Longest Common Subsequence Medium

Problem

Given two strings, return the length of their longest common subsequence: letters that appear in both, in the same order, not necessarily next to each other. "ace" is a common subsequence of "abcde" and "ace".

The five questions

1. State: table[i][j] is the LCS length of the first i letters of text1 and the first j letters of text2.
2. Recurrence: if the last letters match, use both: table[i-1][j-1] + 1. Otherwise drop one last letter or the other: max(table[i-1][j], table[i][j-1]).
3. Base: row 0 and column 0 are 0. An empty prefix shares nothing.
4. Order: rows top to bottom, columns left to right, so above, left, and diagonal are ready.
5. Answer: table[len(text1)][len(text2)].

Solution: 2D table

def lcs_length_2d(text1: str, text2: str) -> int:
    """Length of the longest common subsequence of two strings.

    Args:
        text1: First string.
        text2: Second string.

    Returns:
        The length of the longest subsequence present in both strings.

    Example:
        >>> lcs_length_2d("abcde", "ace")
        3
        >>> lcs_length_2d("abc", "def")
        0
    """
    rows, cols = len(text1), len(text2)
    # table[i][j]: LCS length of text1[:i] and text2[:j].
    # +1 on both sides so row 0 and column 0 exist: the empty prefixes.
    # 0: an empty prefix shares nothing, so row 0 and column 0 stay 0.
    # A comprehension, so each row is its own list.
    table = [[0] * (cols + 1) for _ in range(rows + 1)]

    # i and j count letters used from each string. Start at 1: 0 is the base.
    # rows + 1 and cols + 1 so the full strings are included.
    # Invariant: every row above i is final, and so is row i left of column j.
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            # - 1: a prefix of length i ends with the letter at index i - 1.
            if text1[i - 1] == text2[j - 1]:
                # Match: use both letters. Diagonal answer, + 1 for this letter.
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                # No match: drop text1's last letter (above, i - 1)
                # or text2's last letter (left, j - 1). Keep the better.
                table[i][j] = max(table[i - 1][j], table[i][j - 1])

    # Both full strings.
    return table[rows][cols]

Solution: two rows (Template C)

def lcs_length_rolling(text1: str, text2: str) -> int:
    """Same answer in O(len(text2)) space, keeping only two rows.

    Args:
        text1: First string. Its letters drive the rows.
        text2: Second string. Its letters are the columns.

    Returns:
        The length of the longest subsequence present in both strings.

    Example:
        >>> lcs_length_rolling("abcde", "ace")
        3
    """
    cols = len(text2)
    # previous is the row above. It starts as row 0: empty text1 prefix, all 0.
    # (cols + 1): +1 so slot cols exists. Slot 0 is the empty text2 prefix.
    previous = [0] * (cols + 1)

    # One row per letter of text1.
    # Invariant: previous holds the finished row for the letters before this one.
    for letter in text1:
        # Fresh row. Slot 0 stays 0: an empty text2 prefix shares nothing.
        current = [0] * (cols + 1)
        # j counts text2 letters. Start at 1: slot 0 is the base.
        # cols + 1 so the last letter is included.
        for j in range(1, cols + 1):
            # j - 1: the j-th letter of text2 sits at index j - 1.
            if letter == text2[j - 1]:
                # Match: diagonal (previous[j - 1]) + 1 for this letter.
                current[j] = previous[j - 1] + 1
            else:
                # No match: best of above (previous[j]) and left (current[j - 1]).
                current[j] = max(previous[j], current[j - 1])
        # Row done. It becomes the row above for the next letter.
        previous = current

    # Last row, last slot: both full strings.
    return previous[cols]

This is Template C with combine filled in. The diagonal cell previous[j - 1] is why you need two rows here. Reading it from a single row would see a value already overwritten for this row.

Walkthrough

text1 = "abcde", text2 = "ace". Each bullet is one row, for "" a c e:

• Row a: 0 1 1 1. The a matches, and the 1 carries right.
• Row b: 0 1 1 1. No match, so values copy down.
• Row c: 0 1 2 2. The c matches: diagonal 1, plus 1.
• Row d: 0 1 2 2. No match.
• Row e: 0 1 2 3. The e matches: diagonal 2, plus 1. Answer 3.

Reading the figure. Rows are prefixes of "abcde" and columns are prefixes of "ace". Each amber cell is a letter match, and its green arrow shows it reading the diagonal and adding 1. Blue cells copy the larger of the cell above and the cell to the left. Follow the three green arrows from the top left to the corner. They spell out a, c, e.

Edge cases to raise

• Either string empty: 0, straight from the base row or column.
• Identical strings: the full length.
• No shared letters: 0.
• Asked for the subsequence itself: keep the full 2D table and walk back from the corner. The two-row version cannot rebuild it.
• Put the shorter string on the columns to make the two-row version use O(min(m, n)) space.

7. Edit Distance Medium

Problem

Return the fewest single-letter operations that turn word1 into word2. The allowed operations are insert a letter, delete a letter, and replace a letter. This is the Levenshtein distance.

The five questions

1. State: table[i][j] is the fewest edits to turn the first i letters of word1 into the first j letters of word2.
2. Recurrence: if the last letters match, no edit is needed: table[i-1][j-1]. Otherwise pay 1 and take the cheapest of delete (table[i-1][j]), insert (table[i][j-1]), or replace (table[i-1][j-1]).
3. Base: table[i][0] = i, which is i deletes. table[0][j] = j, which is j inserts.
4. Order: rows top to bottom, columns left to right.
5. Answer: table[len(word1)][len(word2)].

Solution

def edit_distance_2d(word1: str, word2: str) -> int:
    """Fewest inserts, deletes, or replaces that turn word1 into word2.

    Args:
        word1: Source string.
        word2: Target string.

    Returns:
        The edit (Levenshtein) distance.

    Example:
        >>> edit_distance_2d("horse", "ros")
        3
        >>> edit_distance_2d("", "abc")
        3
    """
    rows, cols = len(word1), len(word2)
    # table[i][j]: fewest edits to turn word1[:i] into word2[:j].
    # +1 on both sides so row 0 and column 0 (the empty prefixes) exist.
    # 0 is a placeholder. The base loops and main loop overwrite every cell.
    table = [[0] * (cols + 1) for _ in range(rows + 1)]

    # Base column: turning i letters into "" takes i deletes.
    # rows + 1 so that i = rows is included.
    for i in range(rows + 1):
        table[i][0] = i
    # Base row: turning "" into j letters takes j inserts.
    # cols + 1 so that j = cols is included.
    for j in range(cols + 1):
        table[0][j] = j

    # Start at 1: row 0 and column 0 are the base cases above.
    # Invariant: every row above i is final, and so is row i left of column j.
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            # - 1: a prefix of length i ends with the letter at index i - 1.
            if word1[i - 1] == word2[j - 1]:
                # Last letters already match: no edit, take the diagonal.
                table[i][j] = table[i - 1][j - 1]
            else:
                # 1 for the edit made now, plus the cheapest smaller case.
                table[i][j] = 1 + min(
                    table[i - 1][j],        # delete word1's letter (above)
                    table[i][j - 1],        # insert word2's letter (left)
                    table[i - 1][j - 1],    # replace one with the other (diagonal)
                )

    # Both full words.
    return table[rows][cols]

Walkthrough

word1 = "horse", word2 = "ros". The table ends at 3. One optimal path:

• Replace h with r: horse becomes rorse.
• Delete the second r: rorse becomes rose.
• Delete e: rose becomes ros.
• Check a base cell: table[5][0] = 5, because turning "horse" into "" takes five deletes.

Reading the figure. Rows are prefixes of "horse" and columns are prefixes of "ros". Grey cells are the base row and column, pure inserts or deletes. The amber cells and arrows are one cheapest path. A diagonal step is a replace, or free when the letters match. A down step is a delete. The cost rises by 1 only on the three edit steps, and ends at 3 in the green corner.

Edge cases to raise

• One word empty: the answer is the other word’s length, straight from the base row or column.
• Identical words: 0, all diagonal moves.
• Space follow-up: two rows work, as in LCS. The base row starts as 0, 1, ..., n, and each new row starts with its row number in slot 0.
• Different costs per operation: replace the 1 with that operation’s cost. The shape stays the same.
• Only insert and delete allowed: the answer is m + n - 2 × LCS. Saying that ties the two problems together.