LIS和LCS问题

例题1：最长上升子序列

题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001≤N≤1000，

-10^9 ≤数列中的数≤ 10^9

样例

输入样例：
7
3 1 2 1 8 5 6
输出：
4

(动态规划) O(n^2)

以集合的方式理解DP：最主要的就是状态表示与状态计算

状态表示——集合：表示以第i个数结尾的上升子序列

    ——属性：存储的为最大值（一般为最大值、最小值、数量这三个任意一个）

f[i]就表示为第i个数结尾的最大的上升子序列的个数

状态计算：要求f[i]，你就要知道前i - 1 个数有多少个数比a[i]小，如果比a[i]小那么f[i]的结果就要+1，于是得到转移方程为：f[i] = max(f[i],f[j] + 1)

时间复杂度

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],a[N],n;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++){
        f[i] = 1;                   //表示只选第i个
        for(int j =1 ; j < i; j ++)     //从 j 到 i -1 枚举
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1); //如果满足前面的数比 a[i] 小就更新f[i]
    }

    int res = 0;
    for(int i = 0; i<=n; i ++) res = max(res,f[i]);//找出最大值
    cout << res;
    return 0;
}

例题1：最长上升子序列

题目描述

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数N和M。

第二行包含一个长度为N的字符串，表示字符串A。

第三行包含一个长度为M的字符串，表示字符串B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000

样例

输入：
4 5
acbd
abedc
输出：
3

算法1

(暴力枚举) O(n^2)

这里的状态f[i,j]表示所有在第一个序列中的前i个字母中出现，且在第二个序列的前j个字母中出现的子序列。

——属性为：max

这里难点在于状态计算的划分区间，我们通过选与不选将它分成4种情况：

00表示a[i],b[j]都不选：显然这种情况很好计算，就是f[i-1,j-1]的值，因为新增a[i],b[j]都没用

01表示不选a[i]选a[j]：f[i-1,j]

10表示选a[i]不选a[j]：f[i,j-1]

11表示a[i],b[j]都选：它的计算是f[i-1,j -1] + 1 ，表示在之前的基础之上在加一

难点是第二种和第三种情况：因为f[i - 1,j]和第二种情况并不相等，第二种情况一定是f[i - 1,j]的子集，而f[i - 1,j]又是f[i,j]的子集，所以我们才可以使用f[i-1,j]来代替第二种情况的取值，第三种情况类似，不过再写的时候一般都会忽略第一种情况，因为第一种情况又是第二种和第三种情况的子集~~~

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N];
char a[N],b[N];
int n,m;
int main(){
    cin >> n >> m;
    scanf("%s%s",a + 1, b + 1); // a+1 ,b+1 表示读入从1号下标开始

    for(int i = 1; i <= n; i ++){   //枚举a[i]
        for(int j = 1; j <= m; j++){//枚举b[j]
            f[i][j] = max(f[i - 1][j],f[i][j - 1]);//表示 00 01 10的情况
            if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1] + 1);//当a[i] == b[j] 表示 11这种情况
        }
    }
    cout << f[n][m];        //结果
    return 0;
}

混一下经验，后面将大佬将的背包问题整理出来