最长公共子序列问题。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，用动态规划算法找出X和Y的最长公共子序列并输出，用C/C++实现该算法。

下面是C++实现代码，采用动态规划的思路：

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

const int MAXN = 1005;

int dp[MAXN][MAXN];
char s1[MAXN], s2[MAXN], ans[MAXN];

int main() {
    cin >> s1 >> s2;
    int len1 = strlen(s1), len2 = strlen(s2);
    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]);
            }
        }
    }
    int len = dp[len1][len2];
    int i = len1, j = len2;
    while (i > 0 && j > 0 && len > 0) {
        if (s1[i-1] == s2[j-1]) {
            ans[--len] = s1[i-1];
            i--, j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    cout << ans << endl;
    return 0;
}

输入两个字符串，分别为`s1`和`s2`，然后依据动态规划算法计算`dp`数组，最后根据`dp`数组构造出最长公共子序列，并输出。

代码中的`dp[i][j]`表示`s1`的前`i`个字符和`s2`的前`j`个字符的最长公共子序列的长度，状态转移方程为：

- 如果`s1[i-1] == s2[j-1]`，则`dp[i][j] = dp[i-1][j-1] + 1`
- 如果`s1[i-1] != s2[j-1]`，则`dp[i][j] = max(dp[i-1][j], dp[i][j-1])`

最后，根据`dp`数组构造最长公共子序列，依据以下规则：

- 如果`s1[i-1] == s2[j-1]`，则当前字符为公共字符，往前推进
- 如果`dp[i-1][j] > dp[i][j-1]`，则往上推进
- 如果`dp[i-1][j] <= dp[i][j-1]`，则往左推进

最后输出构造出的最长公共子序列即可。