动态规划解法(C++)

解题思路:

注意事项:

参考代码:

#include <iostream>

using namespace std;

int dp[10001][1001] = {0};

int main()

{

   string a, b;

   cin >> a >> b;

   int m = a.size();

   int n = b.size();

   int res = 0;

   for (int i = 1; i <= m; i++) {

   for (int j = 1; j <= n; j++) {

   if (a[i-1] == b[j-1]) {

   if (dp[i-1][j-1] == j-1) {

       dp[i][j] = j;

   }

   }

   else {

   dp[i][j] = dp[i-1][j];

   }

   res = max(res, dp[i][j]);

   }

   }

   cout << res << endl;

   return 0;

}