【newcoder】最长公共子序列

题目描述

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入描述:

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:

对应每组输入，输出最长公共子序列的长度。

示例1
输入

abcfbc abfcab
programming contest
abcd mnp

输出

4
2
0

原链接

思路

这个题是一个动态规划问题。对于动态规划求解问题，一般有两个特征：①最优子结构；②重叠子问题

①最优子结构

设X = (x1,x2,…xn)和Y = (y1,y2,…ym) 是两个序列，将X和Y的最长公共序列记为LCS(X,Y)

找出LCS(X,Y)就是一个最优化问题。因为需要找到X和Y最长的公共子序列。而要找X和Y的LCS，就需要考虑X的最后一个元素和Y的最后一个元素。
1）如果 xn=ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)

LCS(Xn-1，Ym-1)就是原问题的一个子问题。为什么叫子问题？因为它的规模比原问题小。（小一个元素也是小嘛….）

为什么是最优的子问题？因为我们要找的是Xn-1 和 Ym-1 的最长公共子序列啊。。。最长的！！！换句话说，就是最优的那个。（这里的最优就是最长的意思）

2）如果xn != ym，这下要麻烦一点，因为它产生了两个子问题：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)

因为序列X 和序列Y 的最后一个元素不相等嘛，那说明最后一个元素不可能是最长公共子序列中的元素嘛。（都不相等了，怎么公共嘛）。

LCS(Xn-1，Ym)表示：最长公共序列可以在(x1,x2,….x(n-1)) 和 (y1,y2,…yn)中找。

LCS(Xn，Ym-1)表示：最长公共序列可以在(x1,x2,….xn) 和 (y1,y2,…y(n-1))中找。

求解上面两个子问题，得到的公共子序列谁最长，那谁就是 LCS（X,Y）。用数学表示就是：

LCS=max{LCS(Xn-1，Ym)，LCS(Xn，Ym-1)}

由于条件 1) 和 2) 考虑到了所有可能的情况。因此，我们成功地把原问题转化成了三个规模更小的子问题。

②重叠子问题

重叠子问题是啥？就是说原问题转化成子问题后，子问题中有相同的问题。咦？我怎么没有发现上面的三个子问题中有相同的啊？

OK，来看看，原问题是：LCS(X,Y)。子问题有

❶LCS(Xn-1，Ym-1)   
❷LCS(Xn-1，Ym)   
❸LCS(Xn，Ym-1)

初一看，这三个子问题是不重叠的。可本质上它们是重叠的，因为它们只重叠了一大部分。举例：

第二个子问题：LCS(Xn-1，Ym) 就包含了：问题❶LCS(Xn-1，Ym-1)，为什么？

因为，当Xn-1 和 Ym 的最后一个元素不相同时，我们又需要将LCS(Xn-1，Ym)进行分解：分解成：LCS(Xn-1，Ym-1) 和 LCS(Xn-2，Ym)

也就是说：在子问题的继续分解中，有些问题是重叠的。

由于像LCS这样的问题，它具有重叠子问题的性质，因此：用递归来求解就太不划算了。因为采用递归，它重复地求解了子问题啊。==注意，所有子问题加起来的个数可是指数级的哦。。。==

这张DP表很是重要，从中我们可以窥见最长公共子序列的来源，同时可以根据这张表打印出最长公共子序列的构成路径

具体代码

// write your code here cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        int len1 = str1.length();
        int len2 = str2.length();
        vector<vector<int> >dp(len1,vector<int>(len2,0));
        
        //初始化边界
        dp[0][0] = (str1[0] == str2[0])?1:0;
        for(int i=1;i<len1;i++){
            dp[i][0] = (str1[i] == str2[0])?1:0;
            dp[i][0]  = max(dp[i-1][0],dp[i][0]);
        }
        for(int j=1;j<len2;j++){
            dp[0][j] = (str1[0] == str2[j])?1:0;
            dp[0][j]  = max(dp[0][j-1],dp[0][j]);
        }
        
        // 计算
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                if(str1[i] == str2[j]){
                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        cout << dp[len1-1][len2-1] <<endl;
    }
    return 0;
}