13-动态规划-最长公共子序列
题目
来源
24. 最长公共子序列
思路
不想打字，援引自最长公共子序列 (LCS) 详解+例题模板（全）-CSDN博客
图示举例：
其余详见代码
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N][N];
int main(){
string a,b;
while(cin>>a>>b){
for(int i=1;i<=a.size();i++){ //由于下标是从1开始，故下面的条件判等需要处理一下
for(int j=1;j<=b.size();j++){
if(a[i-1]==b[j-1]){
f[i][j]=f[i-1][j-1]+1;
}else{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
}
cout<<f[a.size()][b.size()]<<endl;//下标从1开始，故可以这么使用，否则下标应该-1
}
return 0;
}