题意:求两个字符串的最长公共子序列的长度。
题目链接:http://poj.org/problem?id=1458
——>>LCS模板题。。
#include <iostream> #include <string> #include <algorithm> #include <cstring> using std::string; using std::cin; using std::cout; using std::endl; using std::max; const int MAXN = 1000 + 10; int dp[MAXN][MAXN]; int Lcs(string strA, string strB) { int nLenA = strA.length(); int nLenB = strB.length(); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= nLenA; ++i) { for (int j = 1; j <= nLenB; ++j) { if (strA[i - 1] == strB[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[nLenA][nLenB]; } int main() { string strA; string strB; while (cin >> strA >> strB) { cout << Lcs(strA, strB) << endl; } return 0; }