​​动态规划算法
  4NlMEXkaC1BZ 2023年11月02日 31 0

以下是一个用C++实现的动态规划算法来解决最长子序列问题(Longest Common Subsequence)的示例代码:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();

    // 创建二维数组dp,并初始化为0
    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];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";

    int result = longestCommonSubsequence(text1, text2);

    cout << "The length of the longest common subsequence is: " << result << endl;

    return 0;
}

以上的代码使用了二维数组dp来记录最长公共子序列的长度。通过遍历字符串text1和text2,根据当前字符是否相等,更新dp数组的值。最后返回dp[m][n]作为最长公共子序列的长度。

请注意,上述代码仅解决了最长公共子序列问题的长度,如果你需要获取具体的最长公共子序列本身(而不仅仅是长度),还需要进行某些额外的操作。


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  LcViZvxOG08L   2023年11月02日   81   0   0 ciiOS#include
4NlMEXkaC1BZ
作者其他文章 更多