最长公共子序列(一)

C++ 解法, 执行用时: 5ms, 内存消耗: 408KB, 提交时间: 2022-05-27

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

using namespace std;

class Solution {
  public:
    int count() {
        getinput();
        vector<int> dp(n);
        for (int i = 0; i < m; i++) {
            int tmp = dp[0];
            if (s1[i] == s2[0])
                dp[0] = 1;
            for (int j = 1; j < n; j++) {
                int temp = dp[j];
                if (s1[i] == s2[j])
                    dp[j] = dp[j - 1] == tmp ? dp[j - 1] + 1 : dp[j - 1];
                else
                    dp[j] = max(dp[j], dp[j - 1]);
                tmp = temp;
            }
        }
        return dp[n - 1];
    }

  private:
    int m;
    int n;
    string s1, s2;
    void getinput() {
        cin >> m >> n;
        if (m < n) {
            cin >> s2 >> s1;
            int tmp = m;
            m = n;
            n = tmp;
        } else
            cin >> s1 >> s2;
    }

    int max(int a, int b) {
        return a > b ? a : b;
    }
};

int main() {
    Solution s;
    cout << s.count();
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 416KB, 提交时间: 2022-04-04

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution{
    public:
    
    int dp(string s1,string s2){
        //s1是短串
        vector<int >dp(s1.size()+1,0);
        vector<int >res(s1.size()+1,0);
        for(int i = 1 ; i <= s2.size();i++){
            for(int j = 1;j <= s1.size();j++){
                //相等时判断上一轮dp上一位的最长序列长
                if(s2[i-1] == s1[j-1]) dp[j] = res[j-1]+1;
                //因为不相等时，可以取当轮dp的最大值，也可是上一轮的本位置dp值
                else dp[j] = max(dp[j-1],res[j]);
            }
            //开始下一位的dp时，更新上一轮的dp值进res
            for(int j = 1;j <= s1.size();j++) res[j] = dp[j];
        }
        return dp[s1.size()];
    }
};

int main(){
    int n,m;
    while(cin>>n>>m){
        string s1,s2;
        cin>>s1>>s2;
        if(s1.size() > s2.size()) swap(s1, s2);
        Solution solo;
        cout<<solo.dp(s1,s2)<<endl;
    }
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 444KB, 提交时间: 2022-05-29

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv)
{
    int n =0, m =0;
    while(cin >> n >> m){
        string str1, str2;
        cin >> str1 >> str2;
        
        if(n > m){
            str1.swap(str2);
            m = n;
            n = str2.size();
        }
        vector<int> dp(n + 1, 0);
        vector<int> dpLast(n + 1, 0);
        for(size_t j = 1; j <= m; j++){
            for(size_t i = 1; i <= n; i++){
                if(str1[i - 1] == str2[j - 1]){
                    dp[i] = dpLast[i - 1] + 1;
                }
                else
                {
                    dp[i] = max(dp[i - 1], dpLast[i]);
                }
                dpLast[i - 1] = dp[i - 1];
            }
            dpLast.back() = dp.back();
        }
        cout << dp[n] << endl;
    }
    
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 484KB, 提交时间: 2022-03-12

// #include <iostream>
// #include <vector>

// using namespace std;

// class solution
// {
// public:
//     int getResult(const string &s1, const string &s2)
//     {
//         int s1Length = s1.length(), s2Length = s2.length();
//         vector<vector<int>> dp(s1Length + 1, vector<int>(s2Length + 1, 0));
        
//         for (int i = 1; i <= s1Length; i++)
//         {
//             for (int j = 1; j <= s2Length; 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[s1Length][s2Length];
//     }
// };

// int main()
// {
//     int n;
//     int m;
//     solution mSolution;
    
//     cin >> n >> m;
//     cin.get();
    
//     string s1, s2;
//     getline(cin, s1);
//     getline(cin, s2);
    
//     cout << mSolution.getResult(s1, s2) << endl;
    
//     return 0;
// }

// #include <iostream>
// #include <vector>

// using namespace std;

// class solution
// {
// public:
//     int getResult(const string &s1, const string &s2)
//     {
//         int s1Length = s1.length(), s2Length = s2.length();
//         vector<vector<int>> dp(s1Length + 1, vector<int>(2, 0));
        
//         int idx = 0;
//         for (int i = 1; i <= s2Length; i++)
//         {
//             for (int j = 1; j <= s1Length; j++)
//             {
//                 if (s2[i - 1] == s1[j - 1])
//                 {
//                     dp[j][idx] = dp[j - 1][idx ^ 1] + 1;
//                 }
//                 else
//                 {
//                     dp[j][idx] = max(dp[j][idx ^ 1], dp[j - 1][idx]);
//                 }
//                 idx ^= 1;
//             }
//         }
        
//         return dp[s1Length][idx ^ 1];
//     }
// };

// int main()
// {
//     int n;
//     int m;
//     solution mSolution;
    
//     cin >> n >> m;
//     cin.get();
    
//     string s1, s2;
//     getline(cin, s1);
//     getline(cin, s2);
    
//     if (n < m)
//     {
//         cout << mSolution.getResult(s1, s2) << endl;
//     }
//     else
//     {
//         cout << mSolution.getResult(s2, s1) << endl;
//     }
    
//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;

int cal(string &s1, const int n, string &s2, const int m){
    vector<vector<int>> dp(2, vector<int>(m+1, 0));
    int ans = 0;
    int idx = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(s1[i] == s2[j]){
                dp[idx][j+1] = dp[idx ^ 1][j] + 1;
            }
            else{
                dp[idx][j+1] = max(dp[idx ^ 1][j + 1], dp[idx][j]);
            }
            //if(dp[idx][j+1] > ans) ans = dp[idx][j+1];
        }
        idx ^= 1;
    }
    ans = dp[idx ^ 1][m];
    return ans;
}
int main(){
    int n, m;
    cin>>n>>m;
    string s1, s2;
    cin>>s1>>s2;
    cout<<cal(s1, n, s2, m);
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 524KB, 提交时间: 2022-06-09

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    
    int len1,len2;
    cin>>len1;
    cin>>len2;
    
    string s1,s2;
    cin>>s1;
    cin>>s2;
    
    vector<int> dpPre(len2+1,0);
    vector<int> dpNext(len2+1,0);
    
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(s1[i-1]==s2[j-1]){
                dpNext[j]=dpPre[j-1]+1;
            }else{
                dpNext[j]=max(dpNext[j-1],dpPre[j]);
            }
        }
        dpPre=dpNext;
    }
    
    cout<<dpNext[len2]<<endl;
    
    return 0;
}

详情