线性 DP 五大经典模型：LIS、LCS、合唱队形、编辑距离详解

数据量达到 10^5 级别时，需要优化。此方法仅能求出长度，无法还原具体路径。

核心思路 维护一个数组 dp[len]，表示长度为 len 的上升子序列中，末尾元素的最小值。利用单调性，通过二分查找找到第一个大于等于当前元素的位置进行替换或扩展。

参考实现

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N], dp[N];
int len;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++) {
        if(len == 0 || a[i] > dp[len]) {
            dp[++len] = a[i];
        } else {
            int l = 1, r = len;
            while(l < r) {
                int mid = (l + r) / 2;
                if(dp[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            dp[l] = a[i];
        }
    }
    cout << len;
    return 0;
}

合唱队形

问题背景 求出一个最长的先递增后递减的子序列长度。本质上是求每个位置作为峰值时，左侧 LIS 与右侧 LDS（最长下降子序列，即反向 LIS）之和的最大值。

关键点 注意峰值元素被计算了两次，最终结果需减一。答案即为总人数减去保留的最多人数。

参考实现

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int a[N], dp1[N], dp2[N];
int n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 正向 LIS
    for(int i = 1; i <= n; i++) {
        dp1[i] = 1;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }

    // 反向 LIS (相当于从右向左的下降)
    for(int i = n; i >= 1; i--) {
        dp2[i] = 1;
        for(int j = n; j > i; j--) {
            if(a[j] < a[i]) dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }

    int ret = 0;
    for(int i = 1; i <= n; i++) {
        ret = max(ret, dp1[i] + dp2[i] - 1);
    }
    cout << n - ret;
    return 0;
}

最长公共子序列 (LCS)

问题背景 给定两个字符串，求它们共有的最长子序列长度。

状态定义 dp[i][j] 表示字符串 s 的前 i 个字符与 t 的前 j 个字符的 LCS 长度。

状态转移

• 若 s[i] == t[j]，则 dp[i][j] = dp[i-1][j-1] + 1。
• 若不等，则取 max(dp[i-1][j], dp[i][j-1])。

参考实现

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int N = 5010;
int dp[N][N];
string s, t;

int main() {
    while(cin >> s >> t) {
        int n = s.size();
        int m = t.size();

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        cout << dp[n][m] << endl;
    }
    return 0;
}

编辑距离

问题背景 将字符串 s 转换为 t 所需的最少操作次数（插入、删除、替换）。

状态定义 dp[i][j] 表示将 s 的前 i 个字符转换为 t 的前 j 个字符的最小代价。

边界处理 空串转换需要特殊初始化：dp[i][0] = i (全删)，dp[0][j] = j (全插)。

状态转移

• 若 s[i] == t[j]，无需操作，dp[i][j] = dp[i-1][j-1]。
• 若不等，取三种操作最小值：
  • 删除：dp[i-1][j] + 1
  • 插入：dp[i][j-1] + 1
  • 替换：dp[i-1][j-1] + 1

参考实现

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int N = 2010;
int dp[N][N];
string s, t;

int main() {
    cin >> s >> t;
    int n = s.size();
    int m = t.size();

    // 初始化边界
    for(int i = 1; i <= n; i++) dp[i][0] = i;
    for(int i = 1; i <= m; i++) dp[0][i] = i;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                int a = dp[i - 1][j] + 1;      // 删
                int b = dp[i][j - 1] + 1;      // 插
                int c = dp[i - 1][j - 1] + 1;  // 改
                dp[i][j] = min({a, b, c});
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

以上五个模型涵盖了线性 DP 的核心逻辑。在实际应用中，重点在于根据题意抽象出正确的状态定义，并分析状态之间的依赖关系。代码实现时注意边界条件与空间复杂度优化。