C++利用递归算法求解两个字符串的最大公共子序列的长度问题

在C++中，我们可以使用递归算法来解决两个字符串的最大公共子序列（Longest Common Subsequence, LCS）问题。最大公共子序列是指两个输入序列中最长的那个子序列，它既不在第一个序列中独占，也不在第二个序列中独占，而是同时存在于两个序列中。

一个常见的递归解决方案是动态规划，特别是使用“主定理”（Master Theorem）。首先定义一个二维数组dp[i][j]，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最大公共子序列长度。递归状态可以表达为：

- 如果s1[i-1] == s2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1，因为当前字符匹配，最长子序列长度加一；
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，意味着要么不包含s1[i-1]，要么不包含s2[j-1]，取这两个情况下的较大值作为结果。

递归函数的基本形式通常是这样的：

int lcsLength(string s1, string s2, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    else if (s1[m-1] == s2[n-1])
        return 1 + lcsLength(s1, s2, m-1, n-1);
    else
        return max(lcsLength(s1, s2, m, n-1), lcsLength(s1, s2, m-1, n));
}