最长公共子序列

tag: 线性DP

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

集合: 记录A的前 $i$ 个字符和B的前 $j$ 个字符的最长公共子序列.

状态计算: $dp[i][j]$ $dp[i-1][j]$ $dp[i][j-1]$ $dp[i-1][j-1]$

因为对 $dp$ 进行的是max算法, 根据max和集合的性质, $dp[i-1][j-1]$ 一定包含在 $dp[i-1][j]$ 和 $dp[i-1][j]$ 中,所以在更新 $dp$ 时, 不需要用到 $dp[i-1][j-1]$ .

对于第 $i$ 和第 $j$ 相等的情况, 有 $dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)$ .

代码如下:

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

const int N = 1010;

int n,m;
int dp[N][N];
char a[N],b[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++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            }
    cout<<dp[n][m];

    return 0;
}