DP on subsequences (LIS / LCS / edit distance)

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.

1. row 0 and column 0 are zeroComparing AB with AC. An empty prefix shares nothing.
2. A against A: a matchThe diagonal held 0, so this cell becomes 1.
3. A against C: no matchTake the better neighbour, which is 1.
4. B against C: no matchNeither side helps, so the cell stays 1.
5. answer = 1The only letter the two share is A.

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;
}

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.

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];
}

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

These phrases in a problem statement point here:

• •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.

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.

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

O(n^2)/O(nm)

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