---
title: "DP on subsequences (LIS / LCS / edit distance)"
url: https://algopath.pro/patterns/dp-subsequence
language: en
summary: "The state here is a pair of positions, one in each of the two sequences. Every cell asks whether those two items match up."
updated: 2026-08-24
---

# DP on subsequences (LIS / LCS / edit distance)

The state here is a pair of positions, one in each of the two sequences. Every cell asks whether those two items match up.

## How does DP on subsequences (LIS / LCS / edit distance) work?

Build a table with one row per item of the first sequence. The columns come from the second.

Cell i and j is the answer for those two prefixes. Nothing past them matters at all.

If the two current items match, the answer grows from the diagonal. Add one to the cell up and left.

If they do not match, drop one item from either side. Take the better of the two neighbouring cells.

Row zero and column zero stand for the empty prefixes. They hold the base values.

Each row reads only the row above it. So one row of memory is enough.

- `row 0 and column 0 are zero` Comparing AB with AC. An empty prefix shares nothing.
- `A against A: a match` The diagonal held 0, so this cell becomes 1.
- `A against C: no match` Take the better neighbour, which is 1.
- `B against C: no match` Neither side helps, so the cell stays 1.
- `answer = 1` The only letter the two share is A.

## When should you use DP on subsequences (LIS / LCS / edit distance)?

- longest increasing subsequence
- longest common subsequence between two strings
- minimum edits to turn one string into another
- keep relative order, may skip items
- diff or alignment between two sequences

## What is DP on subsequences (LIS / LCS / edit distance) confused with?

- **Dynamic programming (1-D)** - One index is enough there. Comparing two sequences needs two of them.
- **DP on strings (word break)** - That page splits a single string into pieces. This one lines two sequences up.
- **Binary search (array)** - The n log n form of increasing subsequence uses binary search. The table form is the slower one.
- **Two pointers (same direction)** - Checking whether one string is a subsequence needs no table. Finding the longest common one does.

## What is the time and space complexity of DP on subsequences (LIS / LCS / edit distance)?

Sequences of length n and m give O(nm) time and memory. Keeping one row cuts memory to O(m).

## A worked example of DP on subsequences (LIS / LCS / edit distance)

### Edit distance between two words

Return the fewest single-character edits that turn one word into another.

An edit inserts, deletes or replaces exactly one character.

Cell i and j holds the cost of turning one prefix into the other.

On a match the cost comes from the diagonal. On a mismatch it is one plus the cheapest neighbour.

```javascript
function minDistance(a, b) {
    // row 0 and column 0 hold the cost of deleting a whole prefix
    const dp = Array.from({ length: a.length + 1 }, (_, i) =>
        Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
    );

    for (let i = 1; i <= a.length; i++) {
        for (let j = 1; j <= b.length; j++) {
            if (a[i - 1] === b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // no edit needed
            } else {
                // replace, delete, insert
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[a.length][b.length];
}
```

## Common mistakes with DP on subsequences (LIS / LCS / edit distance)

- **Confusing a subsequence with a substring** A subsequence may skip items, a substring may not. The transition is not the same.
- **Off by one between table and string** Cell i refers to the character at i minus one. Mixing them shifts every comparison.
- **Filling the base row with zeroes** Edit distance starts with the cost of deleting a whole prefix. Zeroes there give a wrong answer.
- **Using the table when n is large** O(n squared) dies at 1e5 items. Increasing subsequence has an n log n form.

## Which interview problems use DP on subsequences (LIS / LCS / edit distance)?

- **Longest common subsequence** The plain form, over two sequences.
- **Edit distance** Three neighbours to choose from instead of two.
- **Longest increasing subsequence** One sequence, compared against itself.
- **Delete operation for two strings** Total length minus twice the common subsequence.
- **Distinct subsequences** Count the ways rather than the length.
- **Interleaving string** Two sources feeding one target string.
- **Shortest common supersequence** Rebuild the answer by walking the table backwards.

## JavaScript

```javascript
function longestIncreasingSubsequence(arr) {
    const dp = new Array(arr.length).fill(1);
    let best = arr.length ? 1 : 0;
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}
```

## Python

```python
def longest_increasing_subsequence(arr):
    if not arr:
        return 0
    dp = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
```

## PHP

```php
function longestIncreasingSubsequence(array $arr): int {
    $n = count($arr);
    if ($n === 0) return 0;
    $dp = array_fill(0, $n, 1);
    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] < $arr[$i]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }
    return max($dp);
}
```