最长公共子序列长度求解 - 动态规划算法实现

最长公共子序列（Longest Common Subsequence，LCS）是指在两个字符串中找到一个最长的公共子序列，不要求各字符在原串中的位置相邻，返回其长度。

求解最长公共子序列长度可以使用动态规划算法。

设两个字符串分别为 s1 和 s2，长度分别为 m 和 n。定义一个二维数组 dp，其中 dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符的最长公共子序列的长度。则有以下状态转移方程：

当 s1[i] == s2[j] 时，dp[i][j] = dp[i-1][j-1] + 1； 当 s1[i] != s2[j] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])；

最终的最长公共子序列长度为 dp[m][n]。

代码如下：

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.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 (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]);
            } 
        }
    }
    return dp[m][n];
}