C++实现长公共子序列长度 分数 15 作者 王东 单位 贵州师范学院 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。

下面是C++的参考代码实现：

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

const int N = 110;
int dp[N][N];

int main()
{
    string A, B;
    cin >> A >> B;

    int m = A.size(), n = B.size();

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (A[i-1] == B[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[m][n] << endl;

    return 0;
}

其中，使用dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。对于状态转移方程，需要特别注意字符串下标从0开始，因此需要将i和j减1。