DP on subsequences (LIS / LCS / edit distance)

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

With one sequence, dp[i] is the longest increasing chain that ends at item i. Every dp[i] starts at 1, the item on its own.

For each i, look back at every earlier j. If arr[j] is smaller, the chain at j can take arr[i] next.

So dp[i] becomes the larger of itself and dp[j] plus one. The answer is the largest dp[i], not the last one.

With two sequences, build a table instead. Cell i and j is the answer for those two prefixes.

If the two current items match, add one to the cell up and left. If not, take the better of the two neighbouring cells.

Row zero and column zero stand for the empty prefixes. Each row reads only the row above, so one row of memory is enough.

Sources: Wikipedia: Longest common subsequence, Wikipedia: Levenshtein distance, Wagner, Fischer (1974), The string-to-string correction problem

1. arr = [2, 5, 3, 7, 4, 8], every dp = 1Each item on its own is a chain of length 1.
2. dp[1] = 2, dp[2] = 2Both 5 and 3 can follow 2. Nothing else before them is smaller.
3. dp[3] = 37 can follow 5 or 3, and each of those has dp 2. Add one.
4. dp[4] = 34 can follow 3 but not 5 or 7. So it extends 2, 3.
5. dp = [1, 2, 2, 3, 3, 4], answer = 48 follows any earlier item. One longest chain is 2, 5, 7, 8.

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

function longestIncreasingSubsequence(arr: number[]): number {
    const dp = new Array<number>(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;
}

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)

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

    public static int longestIncreasingSubsequence(int[] arr) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int best = arr.length > 0 ? 1 : 0;
        for (int i = 1; i < arr.length; i++) {
            for (int 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;
    }

    public static int LongestIncreasingSubsequence(int[] arr) {
        var dp = new int[arr.Length];
        Array.Fill(dp, 1);
        int best = arr.Length > 0 ? 1 : 0;
        for (int i = 1; i < arr.Length; i++) {
            for (int 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)?

Use DP on subsequences (LIS / LCS / edit distance) when the problem statement says “longest increasing subsequence”, “longest common subsequence between two strings” or “minimum edits to turn one string into another”. A solution built on it usually runs in O(n^2)/O(nm).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

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

DP on subsequences (LIS / LCS / edit distance) is most often confused with Dynamic programming (1-D), DP on strings (word break), Binary search (array) and Two pointers (same direction).

• 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)?

Interview problems solved with DP on subsequences (LIS / LCS / edit distance) include Longest common subsequence, Edit distance, Longest increasing subsequence, Delete operation for two strings, Distinct subsequences, Interleaving string and Shortest common supersequence.

• 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)?

The target complexity of DP on subsequences (LIS / LCS / edit distance) is O(n2)/O(nm).

One sequence of n items costs O(n²) time. Two sequences of n and m cost O(nm), and one kept row is enough.