状态转移方程:
if(st1[i]==st2[j])
res[i+1][j+1]=res[i][j]+1;
else
res[i+1][j+1]= res[i][j+1]>res[i+1][j] ?res[i][j+1]:res[i+1][j] ;
res[i][j]表示字符串字串st1[0-i],st2[0-j]的公共子序列长度。
#include<cstdio> #include <string> #include <iostream> #include <cstring> #include <algorithm> using namespace std; int res[301][301]; int main() { freopen("1.txt","r",stdin); string st1,st2; while(cin>>st1>>st2) { memset(res,0,sizeof(res)); for (int i=0;i<st1.length();i++) { for (int j=0;j<st2.length();j++) { if(st1[i]==st2[j]) res[i+1][j+1]=res[i][j]+1; else res[i+1][j+1]= res[i][j+1]>res[i+1][j] ?res[i][j+1]:res[i+1][j] ; } } cout<<res[st1.length()][st2.length()]<<endl; } }