Two-dimensional dynamic programming

When to use it

Use it when a smaller version of the task needs two numbers to describe it: a place in each of two strings, or a row and a column of a grid.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

A word game gives two words. A run is a group of letters that stand side by side, in the same order, in both words. Return the length of the longest run the two words share.

Input
a = "sand"
b = "islands"

Output
3

The method

1. Make a table of zeros with one extra row and column
2. Go row by row: a cell is one letter of a and one of b
3. Same letters: one more than the cell up and to the left
4. Different letters: no shared run ends here, so 0
5. Return the largest cell

The run, one moment at a time

1. Step 1. The table has a row for each letter of a and a column for each letter of b, plus row 0 and column 0 for no letters. Those stay 0. A ? is a cell not worked out yet.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 ? ? ? ? ? ? ?
   2 a: 0 ? ? ? ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

2. Step 2. A cell stands for one letter of each word. It will hold the length of the shared run that ends with these two letters. The first cell is "s" with "i".

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 ? ? ? ? ? ? ?
   2 a: 0 ? ? ? ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

3. Step 4. "s" and "i" are different, so no shared run ends here. The cell gets 0.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 ? ? ? ? ? ?
   2 a: 0 ? ? ? ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

4. Step 3. "s" and "s" are the same. The cell up and to the left holds 0, so a new run starts here: 0 + 1 = 1.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 ? ? ? ? ?
   2 a: 0 ? ? ? ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

5. Step 3. The cells passed on the way hold 0: their letters differ. "s" and "s" are the same. The cell up and to the left holds 0, so a new run starts here: 0 + 1 = 1.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 0 0 0 0 1
   2 a: 0 ? ? ? ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

6. Step 4. "a" and "l" are different, so no shared run ends here. The cell up and to the left holds 1, the run "s", but that run stops: this cell gets 0.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 0 0 0 0 1
   2 a: 0 0 0 0 ? ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

7. Step 3. "a" and "a" are the same. The cell up and to the left holds 0, so a new run starts here: 0 + 1 = 1.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 0 0 0 0 1
   2 a: 0 0 0 0 1 ? ? ?
   3 n: 0 ? ? ? ? ? ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

8. Step 3. "n" and "n" are the same. The cell up and to the left holds 1, so the run "a" grows to "an": 1 + 1 = 2.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 0 0 0 0 1
   2 a: 0 0 0 0 1 0 0 0
   3 n: 0 0 0 0 0 2 ? ?
   4 d: 0 ? ? ? ? ? ? ?
   

9. Step 3. "d" and "d" are the same. The cell up and to the left holds 2, so the run "an" grows to "and": 2 + 1 = 3.

   b: - i s l a n d s
   0 -: 0 0 0 0 0 0 0 0
   1 s: 0 0 1 0 0 0 0 1
   2 a: 0 0 0 0 1 0 0 0
   3 n: 0 0 0 0 0 2 0 0
   4 d: 0 0 0 0 0 0 3 ?
   

10. Step 5. Every cell is filled. The largest is 3, where "d" meets "d". Up and to the left of it are 2 and 1: the shared run is "and". The bottom right cell holds 0: it is not the answer.

    b: - i s l a n d s
    0 -: 0 0 0 0 0 0 0 0
    1 s: 0 0 1 0 0 0 0 1
    2 a: 0 0 0 0 1 0 0 0
    3 n: 0 0 0 0 0 2 0 0
    4 d: 0 0 0 0 0 0 3 0
    

The code

The numbered comments are the steps of the method.

function solve(a, b) {
  // 1. Make a table of zeros with one extra row and column
  const run = [];
  for (let i = 0; i <= a.length; i++) {
    run.push(Array(b.length + 1).fill(0));
  }
  let best = 0;
  // 2. Go row by row: a cell is one letter of a and one of b
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      // 3. Same letters: one more than the cell up and to the left
      if (a[i - 1] === b[j - 1]) {
        run[i][j] = run[i - 1][j - 1] + 1;
        best = Math.max(best, run[i][j]);
      } else {
        // 4. Different letters: no shared run ends here, so 0
        run[i][j] = 0;
      }
    }
  }
  // 5. Return the largest cell
  return best;
}

def solve(a, b):
    # 1. Make a table of zeros with one extra row and column
    run = []
    for i in range(len(a) + 1):
        run.append([0] * (len(b) + 1))
    best = 0
    # 2. Go row by row: a cell is one letter of a and one of b
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            # 3. Same letters: one more than the cell up and to the left
            if a[i - 1] == b[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                best = max(best, run[i][j])
            else:
                # 4. Different letters: no shared run ends here, so 0
                run[i][j] = 0
    # 5. Return the largest cell
    return best

How to spot it

Given: Two strings to compare, match or turn into each other

A smaller task is a start of one string with a start of the other. Every pair of lengths gets one cell of the table.

Asked: The longest part two strings share, or the fewest edits between them

Look at the last item of each. Whatever is done with them leaves the same question for shorter strings, already answered in the table.

Given: A grid where each move goes only right or down

A cell can be entered only from above or from the left. Its answer comes from those two cells, which are filled first.

Limits: Both strings have up to 1,000 letters

That is about a million pairs of lengths, one cell each, which is fast. Trying every way to line the letters up is not.

Looks like it, but is not

• One list, and the answer at a position depends on a few earlier positions. Use One-dimensional dynamic programming. One number, the position, describes a smaller task there, so one row of cells is enough.
• A grid where you may step in all four directions and want the fewest steps. Use Breadth-first search by distance. A table needs an order in which each cell reads only cells filled before it. Steps in all four directions give no such order.
• A smaller task is a stretch inside one list, from a left end to a right end. Use Interval dynamic programming. That table also has two indices, but both are ends of one stretch. It is filled from short stretches to long ones, not row by row.

Cost and mistakes

Time is the number of cells, rows times columns, written O(m * n), because each cell is filled once from a few neighbors. Extra space is the table. When a row reads only the row above it, keeping one row is enough.

Watch out

• Give the table one extra row and one extra column for no letters at all. Then run[i][j] is about a[i - 1] and b[j - 1], and the cell up and to the left is always there.
• Decide where the answer is from what a cell means. Here a cell is a run that ends at that cell, so the answer is the largest cell. In many tasks it is the bottom right cell.

In the 150

8 problems of the 150 use it. Naming them gives their method away, so the list is folded.