子序列 DP：LIS 与 LCS｜算法讲义

问题#

最长上升子序列（LIS）：从长度为 $n$ 的序列中删除若干元素但保持相对顺序，求最长的严格递增序列。

最长公共子序列（LCS）：分别从字符串 $A$ 、 $B$ 中删除若干字符但保持相对顺序，求两者共有的最长序列。

子序列不要求连续。LIS 只沿一个序列前进，适合定义“以某位置结尾”的一维状态；LCS 同时比较两个序列的前缀，适合定义二维状态。

核心思想与不变量#

LIS：必须以 $a_i$ 结尾#

定义：

dp[i]=\text{以 }a_i\text{ 作为最后一个元素的 LIS 长度}.

枚举此前位置 $j<i$ 。仅当 $a_j<a_i$ 时，才能把 $a_i$ 接到该子序列后：

dp[i]=1+\max_{0\le j<i,\ a_j<a_i}dp[j],

没有合法前驱时 dp[i] = 1。全局答案是 $\max_i dp[i]$ 。同步保存 previous[i]，就能从最优终点反向恢复一条 LIS。

计算到位置 $i$ 时的不变量是：所有 dp[j] (j < i) 都已正确，它们分别代表固定终点的最优解。

延伸阅读（非课程主线）：LIS 的 $O(n\log n)$ 优化#

维护 tails[len - 1]：长度恰为 len 的上升子序列中，最小的末尾值。末尾越小，越容易接上后续元素。对每个 x，在 tails 中用 lower_bound 找第一个大于等于 x 的位置并替换；若不存在则扩展长度。

tails 本身不一定是一条来自原数组的 LIS，但它的长度始终等于当前前缀的 LIS 长度。

LCS：两个前缀#

定义：

dp[i][j]=A[0,i)\text{ 与 }B[0,j)\text{ 的 LCS 长度}.

若末尾字符相同，可以把它接到两个更短前缀的 LCS 后：

dp[i][j]=dp[i-1][j-1]+1.

若末尾字符不同，至少舍弃其中一个：

dp[i][j]=\max(dp[i-1][j],dp[i][j-1]).

从 dp[n][m] 反向移动：字符相同就收集该字符并走向左上，否则走向值更大的相邻状态，即可恢复一个 LCS。

复杂度#

LIS 二重循环：时间 $O(n^2)$ ，状态和前驱空间 $O(n)$ ；
LIS tails 优化：时间 $O(n\log n)$ ，空间 $O(n)$ ；
LCS：时间 $O(nm)$ ，恢复方案时空间 $O(nm)$ ；若只求长度，可滚动为 $O(\min(n,m))$ 空间。

C++17 模板#

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> longest_increasing_subsequence(const vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return {};

    vector<int> dp(n, 1);
    vector<int> previous(n, -1);
    int best_end = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                previous[i] = j;
            }
        }
        if (dp[i] > dp[best_end]) best_end = i;
    }

    vector<int> sequence;
    for (int at = best_end; at != -1; at = previous[at]) {
        sequence.push_back(a[at]);
    }
    reverse(sequence.begin(), sequence.end());
    return sequence;
}

int lis_length_nlogn(const vector<int>& a) {
    // 延伸阅读（非课程主线）：tails + 二分只求长度。
    vector<int> tails;
    for (int value : a) {
        auto position = lower_bound(tails.begin(), tails.end(), value);
        if (position == tails.end()) tails.push_back(value);
        else *position = value;
    }
    return static_cast<int>(tails.size());
}

string longest_common_subsequence(const string& first, const string& second) {
    int n = static_cast<int>(first.size());
    int m = static_cast<int>(second.size());
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (first[i - 1] == second[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string answer;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (first[i - 1] == second[j - 1]) {
            answer.push_back(first[i - 1]);
            --i;
            --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

int main() {
    vector<int> values = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> lis = longest_increasing_subsequence(values);
    cout << "LIS:";
    for (int value : lis) cout << ' ' << value;
    cout << "\nLIS length (n log n extension) = " << lis_length_nlogn(values) << '\n';

    string lcs = longest_common_subsequence("ABCBDAB", "BDCAB");
    cout << "LCS = " << lcs << '\n';
    return 0;
}

示例#

一种可能的输出是：

LIS: 2 5 7 101
LIS length (n log n extension) = 4
LCS = BCAB

最优解可能不唯一，例如 LIS 也可以是 2 3 7 18，LCS 也可能因回溯时的平局选择而不同；只要长度正确并且保持相对顺序即可。

易错点#

LIS 的“严格递增”使用 < 与 lower_bound；若要求非递减，应改为 <= 与 upper_bound。
dp[i] 是“必须以 $i$ 结尾”，因此最终要对所有终点取最大值。
tails 是每个长度下的最优末尾值集合，不应直接当成恢复出的 LIS。
LCS 中字符串下标是 i-1、j-1，而 DP 多开一行一列表示空前缀。
子串要求连续，子序列不要求连续；两类问题不能直接套用同一状态。
LCS 只滚动两行后会丢失普通回溯所需的信息；既要省空间又要恢复答案，需要额外算法。

问题#