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

Source: https://skills101.in/learn/dsa/dsa-dp-grids-and-strings — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

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.

```python
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]]))
```

```text
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)`.

```python
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]]))
```

```text
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](https://skills101.in/learn-img/dsa/lcs-table.svg)

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.

```python
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"))
```

```text
(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:

```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"));
    }
}
```

```text
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](https://skills101.in/learn-img/dsa/edit-distance.svg)

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

```python
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"))
```

```text
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.

```python
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))
```

```text
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.

## 5. Related problems

| Problem | What changes |
|---|---|
| Longest common **substring** (letters must be adjacent) | on a mismatch set `dp[i][j] = 0`; answer = max cell |
| Longest palindromic subsequence | LCS of the string and its reverse |
| Minimum deletions to make two strings equal | `n + m − 2 · LCS` |
| Distinct subsequences, wildcard / regex matching | same 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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-dp-grids-and-strings