题解：AT_past202112_h 最長非共通部分列

· · 题解

这是本蒟蒻的第一篇题解。

前置

题目传送门

AC记录

题目思路

这就是一道最长不公共子序列，我们可以用邪恶美丽的动态规划（DP）解决，首先我们定义 dp 数组为 A 和 B 的最长不公共子序列，接着我们要学会找动态转移方程，这也是学习 DP 最难的知识点之一，可以自己在草稿纸上找一找，画一画；

我们可以发现当 A_{i-1} \ne B_{i-1} 时，则 dp_{ij} = dp_{i-1j-1} + 1，否则 dp_{ij}=\max(dp_{i-1j},dp_{ij-1})。

思路到此为止，建议大家先自己尝试，有不懂的再看一下代码。

代码:

#include<bits/stdc++.h>//万能头
using namespace std;
string a,b;//创建俩个字符串a，b
int dp[5003][5003];//创建二维数组dp
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);//提高运行速度
    cin>>a>>b;//读入
    int lena=a.size();//保存字符串a的长度
    int lenb=b.size();//保存字符串b的长度
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            if(a[i-1]!=b[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[lena][lenb];//答案保存在dp[lena][lenb]
    return 0;//完结散花!!!
}