题意理解

对于字符串，我们可以从其中按照从前往后的顺序随机提取若干字符，这样构成其一个子序列。现对于两个字符串，要求出他们的最长的相同子序列的长度。

方法一

动态规划
定义一个二维数组dp，用来存储s1和s2的最长公共子序列的长度。因为会涉及到i-1和j-1，所以dp[i][j]记录s1[0]~s1[i-1]和s2[0]~s2[i-1]的最长公共子序列的长度maxlen（要注意这里的索引），我们dp数组的第0行和第0列均为0。

从前往后扫描s1和s2，如果s1[i-1]和s2[j-1]的字符相同，那么到此为止的maxlen就要加1；否则就为之前的maxlen。状态转移方程如下：
$d p [i] [j] = d p [i - 1] [j - 1]$ $(s [i - 1] = = s [j - 1])$
$d p [i] [j] = m a x (d p [i - 1] [j], d p [i] [j - 1]$ $(s [i - 1]! = s [j - 1])$

一个案例的示意图如下： alt

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        // write code here
        vector<vector<int>> dp;
        vector<int> row;
        int n = s1.size(), m = s2.size();
        //注意dp数组的大小
        for (int j=0;j<=m;j++)
            row.push_back(0);
        for (int i=0;i<=n;i++)
        {
            dp.push_back(row);
        }
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;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[n][m];
    }
};

时间复杂度： $O (M N)$ 。使用了二重循环，遍历字符串。
空间复杂度： $O (M N)$ 。使用了二维数组dp记录长度，以两个字符串的长度作为行数和列数。

方法二

为了节约空间，我们使用2个一维数组来代替方法一中的二维数组。我们可以发现dp中每一行的值由上一行以及这一行前面的数值直接得到，所以更前面的行不必一直保留。使用数组a记录dp中上一行的值，用数组b记录当前行。当前行计算完毕后，把b赋值给a，同时b清零。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        // write code here
        int a[1001],b[1001];
        int n = s1.size(), m = s2.size();
        //为了满足空间复杂度为min(n,m)
        int len = min(n,m);
        //交换s1,s2，保证s2是较短的，为了正确地做循环
        if (len==n)
        {
            string ss = s1;
            s1 = s2;
            s2 = ss;
        }
        for (int i=0;i<=len;i++)
            a[i]=0;
        
        for (int i=1;i<=s1.size();i++)
        {
            for (int j=1;j<=s2.size();j++)
            {
                if (s1[i-1]==s2[j-1])
                    b[j] = a[j-1] + 1;
                else
                    b[j] = max(b[j-1],a[j]);
            }
            //这里用b覆盖a
            for (int j=0;j<=s2.size();j++)
            {
                a[j] = b[j];
                b[j] = 0;
            }
        }
        return a[s2.size()];
    }
};

时间复杂度： $O (M N)$ 。使用了二重循环，遍历字符串。
空间复杂度： $O (m i n (M, N))$ 。使用了两个一维数组，长度为两个字符串长度的最小值。

题解 | #最长公共子序列(一)#

题意理解

方法一

方法二