DP on subsequences (LIS / LCS / edit distance)

O(n^2)/O(nm)

Track the best subsequence ending at each position: dp[i] for LIS looks back at every earlier smaller item, dp[i][j] for LCS or edit distance walks a 2-D grid over both strings. The answer keeps relative order but is free to skip items.

Signals

longest increasing subsequencelongest common subsequence between two stringsminimum edits to turn one string into anotherkeep relative order, may skip itemsdiff or alignment between two sequences

Template

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

Looks similar, isn't

Dynamic programming (1-D): Plain 1-D dp[i] tracks one running state per index, like the best sum ending here. Subsequence DP instead tracks positions inside one or two SEQUENCES at once (LIS keeps a length ending at index i, LCS and edit distance need a 2-D grid over both strings), because the answer depends on which earlier items you kept, not just the position.

n up to ~1e3..1e4 for the O(n^2) LIS table, or n, m up to ~1e3 each for the O(nm) LCS/edit-distance grid -> quadratic time; patience sorting can cut plain LIS to O(n log n).

Learn this pattern