Skills101

AdvancedData Structures & Algorithms · Lesson 34 of 40 · Updated ·

DP on Grids and Strings — Unique Paths, LCS and Edit Distance

In the previous lesson the state was one number. Many problems need two: a row and a column in a grid, or a position in each of two strings. The state becomes dp[i][j] and the table becomes a 2D grid. The recipe stays the same — state, recurrence, base case, answer — and the table is usually filled row by row, so that the cells a value depends on (above, left, diagonal) are already done.

1. Unique paths in a grid

Problem: a robot starts at the top-left cell of an m × n grid and can move only right or down. How many different paths reach the bottom-right cell?

  • State: dp[i][j] = number of paths from the start to cell (i, j).
  • Recurrence: you enter (i, j) either from above or from the left: dp[i][j] = dp[i − 1][j] + dp[i][j − 1].
  • Base: every cell in the first row and the first column has exactly 1 path (a straight line).

With obstacles, a blocked cell has 0 paths, and the recurrence does the rest.

def unique_paths(grid):              # 0 = free, 1 = blocked
    R, C = len(grid), len(grid[0])
    dp = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if grid[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            else:
                up = dp[i - 1][j] if i > 0 else 0
                left = dp[i][j - 1] if j > 0 else 0
                dp[i][j] = up + left
    return dp[R - 1][C - 1]

print(unique_paths([[0] * 7 for _ in range(3)]))
print(unique_paths([[0, 0, 0],
                    [0, 1, 0],
                    [0, 0, 0]]))
28
2

A 3 × 7 grid has 28 paths. (There is also a formula: you make m − 1 down moves and n − 1 right moves in some order, so the answer is C(m + n − 2, m − 1) = C(8, 2) = 28. The DP is the method that still works once obstacles appear.)

Minimum path sum is the same shape with min instead of +: each cell holds a cost, and dp[i][j] = grid[i][j] + min(up, left).

def min_path_sum(g):
    R, C = len(g), len(g[0])
    dp = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if i == 0 and j == 0:
                dp[i][j] = g[0][0]
            elif i == 0:
                dp[i][j] = dp[i][j - 1] + g[i][j]
            elif j == 0:
                dp[i][j] = dp[i - 1][j] + g[i][j]
            else:
                dp[i][j] = g[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[R - 1][C - 1]

print(min_path_sum([[1, 3, 1],
                    [1, 5, 1],
                    [4, 2, 1]]))
7

The cheapest route is 1 → 3 → 1 → 1 → 1.

2. Longest common subsequence (LCS)

Problem: given two strings, find the length of the longest sequence of letters that appears in both, in the same order (letters do not need to be next to each other). LCS is the idea behind diff tools that compare two versions of a file.

  • State: dp[i][j] = LCS length of the first i letters of a and the first j letters of b.
  • Recurrence:
    • if a[i − 1] == b[j − 1]: the letters match, so dp[i][j] = dp[i − 1][j − 1] + 1;
    • otherwise: drop one letter from either string, dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]).
  • Base: row 0 and column 0 are 0 (an empty string has nothing in common).

LCS table of ABCBDAB and BDCAB with an empty row and column of zeros; the bottom-right cell is 4, and the green cells mark the matched letters B, C, A, B on one best path

To get the letters, not just the length, start at the bottom-right cell and walk back: on a match, take the letter and move diagonally; otherwise move toward the larger of up and left.

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j, out = n, m, []
    while i and j:                         # walk back to rebuild the letters
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[n][m], "".join(reversed(out))

print(lcs("ABCBDAB", "BDCAB"))
print(lcs("placement", "planet"))
(4, 'BCAB')
(5, 'plaet')

The second pair has two best answers of length 5, "plant" and "plaet". The walk-back returns one of them; which one depends on how it breaks ties between up and left.

Time and space are O(n · m). The same in Java:

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];          // Java fills it with 0s
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(lcs("ABCBDAB", "BDCAB"));
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("abc", "xyz"));
    }
}
4
3
0

3. Edit distance (Levenshtein distance)

Problem: the fewest single-letter operations — insert, delete or replace — that turn word a into word b. Spell checkers use it to suggest "placement" when you type "placment".

  • State: dp[i][j] = edit distance between the first i letters of a and the first j letters of b.
  • Recurrence:
    • letters equal: dp[i][j] = dp[i − 1][j − 1] (no operation needed);
    • otherwise 1 + min( dp[i − 1][j] (delete from a), dp[i][j − 1] (insert into a), dp[i − 1][j − 1] (replace) ).
  • Base: dp[i][0] = i (delete all i letters) and dp[0][j] = j (insert all j letters).

Edit distance table turning horse into ros; the first row is 0 1 2 3 and the first column 0 to 5; the bottom-right answer is 3

"horse" → "ros" takes 3 steps: replace h with r (rorse), delete r (rose), delete e (ros).

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete
                                   dp[i][j - 1],      # insert
                                   dp[i - 1][j - 1])  # replace
    return dp[n][m]

print(edit_distance("horse", "ros"))
print(edit_distance("placment", "placement"))
print(edit_distance("kitten", "sitting"))
3
1
3

4. Saving memory

Each row of these tables uses only the row above it (and the current row). So you can keep just two rows and reduce memory from O(n · m) to O(m). For unique paths and min path sum, even one row works: before you update row[j], it still holds the value from above, and row[j − 1] already holds the new value on the left.

def unique_paths_1row(R, C):
    row = [1] * C
    for _ in range(1, R):
        for j in range(1, C):
            row[j] += row[j - 1]          # old row[j] = up, row[j-1] = left
    return row[-1]

print(unique_paths_1row(3, 7), unique_paths_1row(10, 10))
28 48620

The catch: with only one or two rows you lose the full table, so you cannot walk back to rebuild the actual LCS letters. Keep the full table when the problem asks for the sequence itself.

ProblemWhat changes
Longest common substring (letters must be adjacent)on a mismatch set dp[i][j] = 0; answer = max cell
Longest palindromic subsequenceLCS of the string and its reverse
Minimum deletions to make two strings equaln + m − 2 · LCS
Distinct subsequences, wildcard / regex matchingsame 2D table, different recurrence

Common mistakes

  • Off-by-one between string indexes and table indexes: dp[i][j] uses a[i − 1] and b[j − 1] because row 0 means the empty prefix.
  • Forgetting the base row and column in edit distance (they are i and j, not 0).
  • Confusing subsequence (gaps allowed) with substring (no gaps).
  • Building the table with [[0] * m] * n in Python, which makes every row the same list. Use a list comprehension.
  • Optimising memory to two rows and then trying to reconstruct the answer string.

Quick recap

  • 2D state dp[i][j]; fill row by row so up, left and diagonal are ready.
  • Unique paths: up + left; min path sum: cell + min(up, left).
  • LCS: match → diagonal + 1, else max(up, left); walk back from the corner to get the letters.
  • Edit distance: match → diagonal, else 1 + min(delete, insert, replace); base row and column are 0..n.
  • Time O(n · m); memory can drop to one or two rows if you only need the number.

Practice what you learned

📝 Quiz: DP on Grids and Strings5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →