求解最长公共子序列问题。 要求：给出求解算法思路； 并选用一种自己熟悉的编程语言实现； 并分析算法的时间复杂度；（附c++代码）

求解最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的动态规划问题。其基本思路是通过构建一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。

算法步骤如下：
1. 初始化：对于两个空字符串，它们的LCS长度为0，即dp[0][0]=0。
2. 动态填充：从第一个字符开始，如果s1的第i个字符等于s2的第j个字符，那么dp[i][j] = dp[i-1][j-1]+1，因为这个字符可以添加到LCS中；如果不相等，则取之前两对字符LCS的最大值，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 最终结果：当遍历完整个二维数组后，dp[m][n]就是所求的最长公共子序列的长度，其中m和n分别为两个输入字符串的长度。为了获取具体的子序列，可以从dp[m][n]回溯，记录下每个位置上是否匹配以及是否到达边界。

以下是使用C++实现的一个简单版本：

#include <iostream>
#include <vector>

std::string longest_common_subseq(const std::string& s1, const std::string& s2) {
    int m = s1.size();
    int n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 回溯构建LCS
    std::string lcs = "";
    int x = m, y = n;
    while (x > 0 && y > 0) {
        if (s1[x - 1] == s2[y - 1]) {
            lcs += s1[x - 1];
            x--;
            y--;
        } else if (dp[x - 1][y] > dp[x][y - 1])
            x--;
        else
            y--;
    }
    return lcs;
}

int main() {
    std::string s1 = "ABCDGH";
    std::string s2 = "AEDFHR";
    std::cout << "Longest common subsequence: " << longest_common_subseq(s1, s2) << std::endl;
    return 0;
}

时间复杂度分析：动态规划算法的时间复杂度是O(m * n)，其中m和n分别是输入字符串s1和s2的长度。这是因为我们需要填充一个m+1行n+1列的矩阵。