字符串从下标1开始输入,有利于边界情况的分析和初始化。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001;
char x[N];
char y[N];
int dp[N][N];
int main(){
while(cin >> x+1 >> y+1){
//输出的是x,y的长度,如这三组是6 6; 11 7; 4 3
int n = strlen(x+1);
int m = strlen(y+1);
printf("%d %d\n", n, m);
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(x[i] == y[j]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
printf("%d\n", dp[n][m]);
}
return 0;
} 
京公网安备 11010502036488号