本文共 1293 字，大约阅读时间需要 4 分钟。

最长公共子序列（LCS）的问题可以通过动态规划来解决。以下是解决这个问题的详细步骤和代码实现。

方法思路

我们使用一个二维数组 dp[i][j] 来表示在字符串 a 的前 i 个字符和字符串 b 的前 j 个字符中最长公共子序列的长度。方法如下：

通过填充整个二维数组，dp[m][n] 就会给出两个字符串的最长公共子序列的长度。

代码实现

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    string a, b;
    cout << "请输入两个字符串：\n";
    cin >> a;
    cin >> b;
    
    int m = a.size();
    int n = b.size();
    int dp[m+1][n+1];
    
    // 初始化
    for(int i = 0; i <= m; ++i) {
        for(int j = 0; j <= n; ++j) {
            if(i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                if(a[i-1] == b[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
    }
    
    cout << dp[m][n] << endl;
    return 0;
}
    
   

代码解释