c++最长公共子序列

Question

怎么做？
描述

给你一个序列 X 和另一个序列 Z，当 Z 中的所有元素都在 X 中存在，并且在 X 中的下标顺序是严格递增的，那么就把 Z 叫做 X 的子序列。
例如：Z=<a,b,f,c>是序列 X=<a,b,c,f,b,c> 的一个子序列，Z 中的元素在 X 中的下标序列为 <1,2,4,6>。
现给你两个序列 X 和 Y，请问它们的最长公共子序列的长度是多少？

输入描述

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过 100。

输出描述

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例输入 1

abcfbc abfcab
programming contest
abcd mnp
样例输出 1

4
2
0

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestCommonSubsequence(const string &X, const string &Y) {
    int m = X.size();
    int n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

int main() {
    string X, Y;
    while (cin >> X >> Y) {
        cout << longestCommonSubsequence(X, Y) << endl;
    }
    return 0;
}