LIS / LCS_牛客博客

本博客前置知识动态规划

最长上升子序列

给出一个长度为 n 的数组 a ，求其中最长上升子序列的长度？

容易想到的方法

已经学过动态规划的同学很容易会想到一种表示状态和转移状态的方式：
状态表示：dp[i] 计做选出的最长上升子序列以数组中 i 位结尾时，数组中的最长上升子序列长度；
状态转移：如果当前指针指向第 i 个元素， $a_1...a_{i-1}$ 中如果有小于 $a_i$ 的元素，此时可以通过已经记录的 dp 的值向后转移， $i$ 位置结尾的最长上升子序列长度应该再次基础上加一，i 位置结尾的最长上升子序列长度就是这些能转移过来的状态的最大值。
初始状态：初始状态时 dp[i] 的位置最长上升子序列的长度没有更新过，一个序列中最短的最长上升子序列长度是1，直接置为1即可。

然后是简短的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
inline int read() {
    int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int a[maxn],dp[maxn],ans;
int main() {
    int n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), dp[i] = 1;
    for(int i = 2; i <= n; i++) 
        for(int j = 1; j < i; j++) 
            if(a[i] > a[j]) 
                dp[i] = max(dp[i],dp[j] + 1), ans = max(ans,dp[i]);
    cout << ans << endl;
}

上面的代码可以轻易发现时间复杂度是 $O(n ^ {2})$ 的。

LIS

符号约定：
len：当前最大上升子序列长度
同样是动态规划的思想，这样考虑这三个问题：
状态表示：dp[i] 表示最长上升子序列长度为 i 时，最后一位数字最小是什么。
状态转移：当前位置假设为 i ，将 $a_i$ 和之前记录的 dp[len] 的值来比较，如果 $a_i$ 比之前最长上升子序列的最后一位还大，那可以得到以 $a_i$ 结尾的长度是len + 1的新的最长上升子序列。如果 $a_i$ 小于等于之前最长上升子序列的最后一位，那 $a_i$ 可以用来更新其他位置的状态，用二分加速从 $dp[1]...dp[len]$ 中找出第一个大于等于 $a_i$ 的数字，这个地方表示该最长上升子序列中最后一位数的最小值，这个数字是可以更小的，将这个数字改为 $a_i$ 。
初始状态：初始时dp表示的最大上升子序列长度是1，最后一位是 $a_1$ 。

简短的代码部分

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 6;
int a[maxn],dp[maxn];
inline int read() {
    int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int main(){
    int n = read(), len = 1;
    for(int i = 1; i <= n; i++) a[i] = read();
    dp[1] = a[1];
    for(int i = 2; i <= n; i++)
        if(a[i] > dp[len]) dp[++len] = a[i];
        else dp[lower_bound(dp + 1, dp + len + 1, a[i]) - dp] = a[i];
    cout << len << endl;
}

时间复杂度是优秀的O(nlogn)

如果还是不能理解这部分，可以看下面的例子
有8个数字的数组，数字: 5 3 4 2 1 7 9 8;
初始时刻我们令dp[1] = a[1] , len = 1。
图片说明
指针指向 $a_2$ ，这个数字数3，小于数字dp[len]，那么从1 ... len中查找第一个大于等于3的数字，是dp[1]，将dp[1]修改为3。

指针指向 $a_3$ ，这个数字是4，大于数字dp[len]，len++，后一位计做4。

指针指向 $a_4$ ，这个数字是2，小于数字dp[len]，那么从1 ... len中查找第一个大于等于2的数字，是dp[1]，将dp[1]修改为2。
图片说明
指针指向 $a_5$ ，这个数字是1，小于数字dp[len]，那么从1 ... len中查找第一个大于等于1的数字，是dp[1]，将dp[1]修改为1。

指针指向 $a_6$ ，这个数字是7，大于数字dp[len]，len++，后一位计做7。

指针指向 $a_7$ ，这个数字是9，大于数字dp[len]，len++，后一位计做9。
图片说明
指针指向 $a_8$ ，这个数字是8，小于数字dp[len]，那么从1 ... len中查找第一个大于等于8的数字，是dp[4]，将dp[4]修改为8。

已经查找完全部的数字，len = 4，就是最长上升子序列的长度。

最长公共子序列

给出一个长度为 $n$ 的数组 $a$ ，一个长度为 $m$ 的数组 $b$ ，求出其中最长公共子序列长度？
注意区分最长公共子序列和最长公共字串，最长公共子串一定是在每一个数组中都是连续的，但最长公共子序列不一定连续。

依然用动态规划的方法考虑三个问题，
状态表示：dp[i][j]表示第一个序列到i位置为止，第二个序列到j位置为止，最长的公共子序列长度
状态转移：解决这个问题要针对两个位置，第一个数组中的第i位，第二个数组中的第j位，比较容易想到可以从i - 1和j - 1位置转移过来，如果第i位和第j位的数字相同，那么dp[i][j]的值就是dp[i - 1][j - 1]的值加1，但是这样考虑是不完全的，因为b[j]不一定会只和a[i]相等，b[j]还可能与a数组第i位之前的数字相等，仔细回想，求dp数组时循环是下标从小到大跑的，dp[i - 1][j]保存的状态就是b[j]可能和a数组第i位之前的数字可能相等时的状态，所以状态转移要算上dp[i - 1][j]，同样a[i]还可能与b数组第j位之前的数字相等，还需要算上dp[i][j - 1]，这三个值中取出一个最大值作为dp[i][j]的值。
初始状态：因为不知道是否存在相同的序列，所以全部置零即可。

如果要找出这个最长公共序列呢，倒序寻找状态转移的位置即可。
简短的代码部分：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 4;
inline int read() {
    int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int a[maxn], b[maxn], dp[maxn][maxn], k, path[maxn];
int main() {
    int n = read(), m = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= m; i++) b[i] = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = max(dp[i - 1][j], max(dp[i][j - 1], dp[i - 1][j - 1] + (a[i] == b[j])));
    cout << dp[n][m] << endl;
    int i = n, j = m;
    while(dp[i][j])
        if(dp[i][j] == dp[i - 1][j]) i--;
        else if(dp[i][j] == dp[i][j - 1]) j--;
        else path[++k] = a[i], i--, j--;
    for(int i = k; i >= 1; i--) printf("%d%c",path[i],i == 1 ? '\n' : ' ');
}