编辑代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    // 初始化dp数组
    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];  // 返回最长公共子序列的长度
}

int main() {
    string s1 = "ABCD";
    string s2 = "ABCFB";
    int length = longestCommonSubsequence(s1, s2);
    cout << "最长公共子序列的长度为：" << length << endl;
    return 0;
}