最长公共子序列(一)

题意

给定一个两个字符串，求它们的公共子序列的长度

方法

深搜(TLE)

分析

用两个指针分别指向两个字符串当前比对的位置

如果相等，则计数+1向后比较，递归继续

如果不等，舍去其中一个字符串你的位置，递归继续

所有方案中的最大长度，就是要求的值。

变成伪代码就是

dfs(位置i0,位置i1):
	if s0[i0] = s1[i1]:
		ans = 1 + dfs(i0+1,i1+1) // 相等
    else:
		ans = max(
            	dfs(i0+1,i1), // 舍去其中一个字符串的位置
            	dfs(i0,i1+1) // 舍去其中一个字符串的位置
        		)

代码

class Solution {
public:
    int dfs(string & s0,string & s1,int i0,int i1){
        if(i0 >= s0.size() || i1 >= s1.size()) return 0;
        if(s0[i0] == s1[i1]){
            return dfs(s0,s1,i0+1,i1+1) + 1;
        }
        return max(
            dfs(s0,s1,i0+1,i1),
            dfs(s0,s1,i0,i1+1)
        );
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        return dfs(s1,s2,0,0);
    }
};

复杂度分析

时间复杂度: 最坏情况，两两不等，对于每一层都有两个分支，所以总时间复杂度为$O(2^{n+m})O(2^\{n+m\})$

空间复杂度: 空间主要消耗在递归层数，递归层数不超过数组长度之和，所以空间复杂度为$O(n+m)O(n+m)$

动态规划

分析

上面的深搜方法，对较深的位置，有大量的重复搜索，而实际上，对于当两个指针为定值时，向后的最长公共子序列长度是唯一的值，反过来讲，即是只需要关心这个两个指针前面部分的最长公共子序列的长度。

于是用dp[i][j]表示，从第一个字符串开头到i且选则i，第二个字符串开头到j且选则j的最大公共子序列的长度

if s0[i] == s1[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i][j-1],dp[i-1][j])

样例

以题目样例数据"abcde","bdcaaa"为例

所以最后输出2即可

代码

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

复杂度分析

空间复杂度: 状态是两个字符串长度相乘，所以空间复杂度为$O(nm)O(nm)$

时间复杂度: 状态转移，仅与它相邻的三个值相关，是常数代价, 所以时间复杂度为$O(nm)O(nm)$