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

【模板】最长上升子序列

题目描述

题目解析

本题介绍最长上升子序列的推广解法，当数据量较大时用这种解法。 这里会利用贪心加二分优化时间复杂度，但是需要注意，这种方式是有局限性的，它只能求出最长上升子序列的长度，而不能还原出整个最长上升子序列。

在研究最长上升子序列时，其实只用关心序列的长度和序列最后一个元素是谁，我们并不关心序列具体长什么样子，本题是求解思路就是基于此实现的。

1. 状态表示 对于原序列来说，我们先找出所有长度刚好是 i 的上升子序列（比如 i=3 时，就是所有长度为 3 的上升子序列），然后把这些子序列的最后一个数都列出来，在这些数里找最小的那个，这个最小的数就是 dp[i]。 这里用最小值充当 dp[i] 是用到了贪心的思想：要让序列尽可能长，就要让序列末尾元素尽可能小，让序列后面能挂更多元素。

2. 状态转移方程 除了 dp 数组，还需要用一个全局变量 len 来存储最长上升子序列的长度。 填 dp 数组时我们要遍历整个 a 数组，首先处理边界情况，当 len 为 0（序列为空）或者 a[i] 比 dp[len] 大（a[i] 比最长序列的末尾元素还大）时，直接把 len++，然后把 a[i] 赋值给 dp[len]。否则就是一般情况，也就是序列本身已经有元素了，并且 a[i] 的值小于最长序列的末尾元素，这时我们要更新 dp 数组，但是 len 保持不变，更新策略是在 dp 数组中二分查找所有大于等于 a[i] 的元素中，其中的最小值所在的位置，然后把 a[i] 的值赋给该位置。（本质就是维护 dp 数组的特性：dp[i] 为长度为 i 的所有子序列末尾元素的最小值）

3. 初始化 无。

4. 填表顺序 从左往右。

5. 输出结果 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];
    }

    // 遍历原数组并填 dp 数组
    for (int i = 1; i <= n; i++) {
        if (len == 0 || a[i] > dp[len]) {
            // 边界情况，len 和 a[i] 大于最长合法序列的末尾元素时
            // 直接把 a[i] 放在 dp 数组 ++len 处
            dp[++len] = a[i];
        } else {
            // 在 dp 数组中二分查找大于等于 a[i] 的最小值
            int l = 1, r = len;
            while (l < r) {
                int mid = (l + r) / 2;
                if (dp[mid] >= a[i]) {
                    // 答案在左半部分，包含 mid
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            // 把 a[i] 赋值给查找到的 dp 数组中大于等于 a[i] 的最小值
            dp[l] = a[i];
        }
    }
    cout << len;
    return 0;
}

合唱队形

题目描述

题目解析

本题是最长上升子序列问题的一个模板题，比较简单。 依据题意，要找一个最长的先递增在递减的子序列，要让该子序列最长，就要分别让递增序列和递减序列都尽可能长，最终答案就是遍历所有同学找到一个同学 i，以他为顶峰的递增序列 + 递减序列长度是最大的，但是需要注意同学 i 既在递增序列中也在递减序列中，相当于递增序列 + 递减序列把同学 i 算了两遍，所以最终答案要减一。

所以我们要对每一个同学求他的最长的递增子序列和最长递减的子序列，求最长递减的子序列也就相当于求从右往左的最长递增子序列，根据求最长的递增子序列的通用方法，我们知道 dp[i] 就表示以 i 结尾的所有子序列中，最长的上升子序列。本题我们要开两个 dp 数组，分别维护从左往右的最长递增子序列和从右往左的最长递增子序列。

代码

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

const int N = 110;
// dp1 维护从左往右的最长上升子序列
// dp2 维护从右往左的最长上升子序列
int a[N], dp1[N], dp2[N];
int n;

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

    // 初始化
    // 按序填表
    // 1. 填 dp1 数组
    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);
        }
    }

    // 2. 填 dp2 数组
    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++) {
        // 因为中间 i 的同学算了两遍，所以需要减一
        ret = max(ret, dp1[i] + dp2[i] - 1);
    }
    cout << n - ret;
    return 0;
}

牛可乐和最长公共子序列

题目描述

题目解析

痛点：存储字符串问题！用 string 存储下标从 0 开始！ 解决方案：

1. 修改下标映射：i -> i - 1, j -> j - 1
2. s = " " + s; t = " " + t;

本题不仅会讲题解，还会介绍一下如何分析两个数组的 dp 问题。

1. 初始化 用一个二维数组 dp[i][j]，表示 s 字符串 1 到 i 区间内和 t 字符串 1 到 j 区间内，所有子序列中，最长公共子序列的长度。

2. 状态转移方程 状态转移方程要分两种情况讨论：

3. 当遍历到两个字符串相同的元素时（s[i] == t[j]），表示这个相同的元素的最长公共子序列的元素之一，要把这个这一对相同的元素选上，也就是把当前公共子序列长度在之前的基础上加 1，那要如何找到之前的公共子序列长度呢？其实之前的公共子序列长度就是 s 字符串 1 到 i - 1 区间内和 t 字符串 1 到 j 区间内的最长公共子序列的长度，也就是 dp[i - 1][j - 1]，所以这种情况的状态转移方程： dp[i][j] = dp[i - 1][j - 1] + 1

4. 当遍历到两个字符串不同的元素时（s[i] != t[j]），一定不会把这一对不同的元素选到，这时为了填 dp[i][j] 就需要退而求其次，求在不看 s[i] 的情况下的最长公共子序列、在不看 t[j] 的情况下的最长公共子序列和求在不看 s[i] 并且不看 t[j] 的情况下的最长公共子序列，也就是分三种情况讨论： 在 s 数组的 1 到 i 区间和 t 数组的 1 到 j - 1 区间找最长公共子序列 在 s 数组的 1 到 i - 1 区间和 t 数组的 1 到 j 区间找最长公共子序列 在 s 数组的 1 到 i - 1 区间和 t 数组的 1 到 j-1 区间找最长公共子序列 dp[i][j] 就是在这三种情况中取最值，但对于这种三种情况中取最值的逻辑，因为情况 3 是包含在情况 1、2 中的，所以情况 3 的方案一定小于等于情况 1、2，所以在前两种情况中取最值即可。 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

3. 初始化 全部为 0 即可，因为本题的长度必定大于 0，0 不会干扰 max 取最大值的逻辑。 本题虽然是多组测试用例，但是填表是覆盖并且有顺序的，所以每组用例不用重置。

4. 填表顺序 根据状态转移方程，填 [i][j] 时会用到左、上、和左上三个位置的格子，所以填表顺序是从上往下、从左往右。

5. 输出结果 假设 s 字符串长度为 n，t 字符串长度为 m: dp[n][m]

代码

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

编辑距离

题目描述

题目解析

1. 状态表示 本题思路继续延续上一题的双数组 dp 问题，状态表示也类似：dp[i][j] 表示把 s 字符串的 1 到 i 子字符串变成 t 字符串的 1 到 j 子字符串的最少操作次数。

2. 状态转移方程 还是和上一题类似分两种情况讨论：

3. 当遍历到两个字符串相同的元素时（s[i] == t[j]），说明此时不需要修改 s 数组最后一个元素，也就是对于 dp[i][j] 来说不需要将操作数加一，仅需要拿到把 s 字符串的 1 到 i - 1 子字符串变成 t 字符串的 1 到 j - 1 子字符串的最少操作次数即可，拿到的该最少操作次数为 dp[i][j] 的取值。

4. 当遍历到两个字符串不同的元素时（s[i] != t[j]），说明此时需要修改 s 数组最后一个元素，因为题目给出了三种修改方式，所以这里我们要分三种情况讨论：

   1. 删除 s 字符串最后一个元素，然后把 s 字符串的 1 到 i - 1 子字符串变为 t 字符串，把 s 字符串的 1 到 i - 1 子字符串变为 t 字符串的最少操作次数在 dp[i - 1][j] 中，因为有删除操作，所以还需要加 1。dp[i][j] = dp[i - 1][j] + 1
   2. 在 s 字符串最后面插入 t 字符串的最后一个元素，然后把 s 字符串的 1 到 i 字符串变为 t 字符串的 1 到 j - 1 子 t 子字符串。dp[i][j] = dp[i][j - 1] + 1
   3. 把 s 字符串最后一个元素改为 t 字符串最后一个元素，然后把 s 字符串的 1 到 i - 1 子字符串变为 t 字符串的 1 到 j - 1 子字符串。dp[i][j] = dp[i - 1][j - 1] + 1

5. 初始化 本题初始化需要结合题目的实际意义，虽然题目数据范围的字符串长度从 1 开始，但是对于本题来说，研究字符串为空时还是有必要的，当把一个空串转换为一个长度为 1 的字符串时最少字符操作次数是 1（插入 1 次），同理把一个空串转换为一个长度为 2 的字符串时最少字符操作次数是 2，所以对于 dp 数组的边界情况 dp[0][1] 要初始化为 1，dp[0][2] 要初始化为 2，依次类推。 当把长度为 1 的字符串转换为一个空串时最少字符操作次数是 1（删除一次），同理当把长度为 2 的字符串转换为一个空串时最少字符操作次数是 2，所以对于 dp 数组的边界情况 dp[1][0] 要初始化为 1，dp[2][0] 要初始化为 2，依次类推。

4. 填表顺序 从上往下，从左往后。

5. 输出结果 dp[n][m]

代码

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