C++最长公共子序列

最长公共子序列是指在两个字符串中找到一个最长的序列，使得该序列在两个字符串中的字符顺序保持一致。比如对于字符串"abcfbc"和"abfcab"，它们的最长公共子序列是"abcb"。

C语言可以用动态规划来解决最长公共子序列问题。动态规划的思路是，定义一个二维数组dp，其中dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。然后根据字符串1和字符串2的字符是否相等来更新dp数组。具体的更新规则是，如果字符串1的第i个字符和字符串2的第j个字符相等，那么dp[i][j]就等于dp[i-1][j-1]+1；否则，dp[i][j]等于dp[i-1][j]和dp[i][j-1]中的较大值。最后，dp[m][n]就是最长公共子序列的长度，其中m和n分别表示字符串1和字符串2的长度。

相关问题

c++最长公共子序列

最长公共子序列问题是指给定两个字符串s1和s2，求它们的最长公共子序列（LCS）的长度。

解决该问题可以采用动态规划的思想，具体过程如下：
1. 定义状态：dp[i][j]表示s1的前i个字符与s2的前j个字符的LCS长度。
2. 初始化状态：dp[j]=dp[i]=0，表示空串与任意字符串的LCS长度都为0。
3. 状态转移方程：
当s1[i-1] = s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；
当s1[i-1] ≠ s2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 最终结果：dp[m][n]，其中m和n分别为s1和s2的长度。

以下是C++代码实现：

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.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(text1[i-1] == text2[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];
}

c++最长公共子序列代码

C++中求最长公共子序列的代码，可以使用动态规划算法来实现。具体实现步骤如下：

1. 定义两个字符串s1和s2，分别表示要求最长公共子序列的两个字符串。

2. 定义一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度。

3. 初始化dp数组的第一行和第一列为0，即当其中一个字符串为空时，最长公共子序列长度为0。

4. 遍历s1和s2的每个字符，如果s1[i]等于s2[j]，则dp[i][j]等于dp[i-1][j-1]+1；否则dp[i][j]等于max(dp[i-1][j], dp[i][j-1])，即分别取不包含当前字符的情况下的最长公共子序列长度的最大值。

5. 最终dp[s1.size()][s2.size()]即为最长公共子序列的长度。

以下是C++代码实现：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    int dp[m+1][n+1];
    for(int i = 0; i <= m; i++) dp[i] = 0;
    for(int j = 0; j <= n; j++) dp[j] = 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", s2 = "ACDF";
    cout << "The length of the longest common subsequence is: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}