Common Subsequence 动态规划
#include<bits/stdc++.h>
using namespace std;
const int Max=1002;
int dp[Max][Max];
int main() {
char s1[Max];
char s2[Max];
while(cin>>s1+1>>s2+1) {
int n=strlen(s1+1);
int m=strlen(s2+1);
int answer=0;
for(int i=0; i<=n; i++) {
for(int j=0; j<=m; j++) {
if(i==0||j==0) {
dp[i][j]=0;
continue;
}
if(s1[i]==s2[j]) {
dp[i][j]=dp[i-1][j-1]+1;
} else {
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
answer=max(answer,dp[i][j]);
}
}
cout<<answer<<endl;
}
return 0;
}
using namespace std;
const int Max=1002;
int dp[Max][Max];
int main() {
char s1[Max];
char s2[Max];
while(cin>>s1+1>>s2+1) {
int n=strlen(s1+1);
int m=strlen(s2+1);
int answer=0;
for(int i=0; i<=n; i++) {
for(int j=0; j<=m; j++) {
if(i==0||j==0) {
dp[i][j]=0;
continue;
}
if(s1[i]==s2[j]) {
dp[i][j]=dp[i-1][j-1]+1;
} else {
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
answer=max(answer,dp[i][j]);
}
}
cout<<answer<<endl;
}
return 0;
}
”