求两个字符串的最长公共子序列的长度. 输入:第一行字符串S1,第二行字符串 S2 (1<=字符串长度<=1000).输出:数字M,为最长公共子序列长度.测试用例如下: 输入 BDCABA ABCBDAB 输出 4 BCBA BCAB BDAB

你好！感谢提供问题。以下是求解两个字符串最长公共子序列长度的程序，代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int len1 = s1.length(), len2 = s2.length();

    memset(dp, 0, sizeof(dp)); // 初始化

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[len1][len2] << endl; // 输出结果
    return 0;
}

该程序采用动态规划算法，建立一个二维数组dp[i][j]表示s1中前i个字符与s2中前j个字符组成的最长公共子序列长度。对于每个i和j，分两种情况计算dp[i][j]：

① 如果s1[i-1] == s2[j-1]，即当前字符相等，那么这个字符肯定在最长公共子序列中，所以dp[i][j]=dp[i-1][j-1]+1。

② 如果s1[i-1] != s2[j-1]，即当前字符不相等，那么最长公共子序列肯定不包括这两个字符。因为长度是最长的，所以取dp[i-1][j]和dp[i][j-1]的较大值作为dp[i][j]的值。

这样，我们就可以得到最长公共子序列的长度，输出即可。