当前位置：首页 > news >正文

【39. 最长公共子序列】

news 来源：原创 2024/5/17 13:09:23

思路

第一个字符串是a,第二个字符串是b。
划分依据（划分成四个子集）
- 是以a[i]和b[j]是否包含在子序列当中
- 一共四种情况a[i],a[j],a[i][j],都不选
- 把f[i][j]所有的子序列全部都分到这四种情况
- f[i][j]的最大值是我们这四个集合的最大值，再取max

在这里插入图片描述

注意

对于0 1 是序列不包含a[i],但是一定包含b[j],而f[i-1][j]是所有在第一个序列前i - 1个字母出现，且在第二个序列的前j个字母出现的子序列,所以f[i-1][j]包含0 1集合，所以可以用f[i-1][j]代替0 1 集合的最大值。
而且对于第一种集合f[i-1][j-1]可以不写，因为集合2（f[i-1][j]）与集合3（f[i][j-1]包含了集合1的情况

可以代替的原因

对于DP问题，属性有三种max, min, 数量
例子:
- 求A,B,C的最大值，我们可以先求max(A,B),max(B,C),然后再求这俩个max的最大值。而这里B出现了俩次，所以对于求最大值和最小值的可以使用该方法，而求数量就不可以

总结：

在这里插入图片描述

题目

在这里插入图片描述

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];     //字符串a和b
int f[N][N];

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            
            //因为最后一个集合a[i]和b[i]，不一定存在，只有当序列a的第i个值与序列b的第j个值相等才可以
            //序列a是以i结尾，序列b是以j结尾，所以只有相等，才有可能是公共子序列
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
        
       
        
    }
     cout << f[n][m];
    return 0;
}