最长公共子序列长度（dp）

/// 求两个字符串的最大公共子序列长度，最长公共子序列则并不要求连续，但要求前后顺序（dp）

#include <bits/stdc++.h>

using namespace std;

void Print(int i, int j){

}

int main()

{

    string str1,str2;

    cin >> str1 >> str2;

    int len1 = str1.length();

    int len2 = str2.length();

    vector<vector<int>> dp(1000, vector<int> (1000, 0));

    for(int i = 1; i <= len1; i++)

    {

        for(int j = 1; j <= len2; j++)

        {

            if(str1[i - 1] == str2[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[len1][len2] << endl;

    return 0;

}

巴特西

最长公共子序列长度（dp）

最新文章

热门文章