字符串从下标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; }