C++ 解法, 执行用时: 5ms, 内存消耗: 400KB, 提交时间: 2021-11-20

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        int s1size=s1.size();
        int s2size=s2.size();
        const char *ps1=s1.c_str();
        const char *ps2=s2.c_str();
        if(s1size<s2size) {
            swap(s1size, s2size);
            swap(ps1, ps2);
        }
        
        vector<int> dp(s2size+1, 0);
        for(int i=1;i<=s1size;++i) {
            int prev=dp[0];
            for(int j=1;j<=s2size;++j) {
                int tmp=dp[j];
                if(ps1[i-1]==ps2[j-1]) {
                    dp[j]=prev+1;
                }
                else if(dp[j-1]>dp[j]) {
                    dp[j]=dp[j-1];
                }
                prev=tmp;
            }
        }
        
        return dp[s2size];
    }
};

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        // write code here
        int size=min(s1.size(),s2.size());
        int pre;
        int sizedul=max(s1.size(),s2.size());
        vector<int> dp(s2.size()+3,0);
        for(int i=1;i<=s1.size();i++){
            pre=0;dp[0]=0;
            for(int j=1;j<=s2.size();j++){
                int cur=dp[j];
                if(s1[i-1]==s2[j-1]){
                    dp[j]=pre+1;
                }
                else{
                    dp[j]=max(dp[j],dp[j-1]);
                }
                pre=cur;
            }
        }
        return dp[s2.size()];
    }
};

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
	int LCS(string s1, string s2)
	{
		int n = s1.size();
		int m = s2.size();
        if(n == 0|| m == 0) return 0;
		if (n < m)//n长，m短
		{
			swap(n, m);
			std::swap(s1, s2);
		}
		vector<int> buff(m, 0);
		for (int i = 0; i < n; i++)
		{
			int lastVal = 0;
			for (int j = 0; j < m; j++)
			{
				int temp = s1[i] == s2[j] ? lastVal + 1 : lastVal;
				lastVal = buff[j];
				if (j > 0) temp = max(temp, buff[j - 1]);
				buff[j] = max(temp, buff[j]);
			}
		}
		return buff[m - 1];
	}
};

C++ 解法, 执行用时: 6ms, 内存消耗: 404KB, 提交时间: 2022-05-14

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        // write code here
        int n = min(s1.size(),s2.size());
        vector<int> a(n+1,0);
        vector<int> b(n+1,0);

        if(s1.size()<s2.size())
            swap(s1,s2);

        for(int i = 1; i<=s1.size();++i){
            for(int j = 1; j<=s2.size(); ++j)
            {
               if(s1[i-1] == s2[j-1])
                   a[j] = b[j-1] + 1;
                else
                    a[j] = max(a[j-1],b[j]);
            }
            swap(a, b);
            a =  vector<int>(n+1,0);
        }
        return b[n];
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 404KB, 提交时间: 2022-03-14

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string x1, string x2) {
        // write code here
        vector<int> dp(x1.size()+1,0),his(x1.size()+1,0);
        for(int i=0;i<x2.size();i++)
        {
            for(int j=0;j<x1.size();j++)
                if(x2[i]==x1[j])
                  dp[j+1]=his[j]+1;
            else
              dp[j+1]=max(dp[j],dp[j+1]);
            for(int k=0;k<=x1.size();k++)
               his[k]=dp[k];
        }
        return dp[x1.size()];
    }
};