动态规划：1132: 最长公共子序列

题目描述

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

输入

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例输入

abcfbc abfcab
programming contest
abcd mnp

样例输出

4
2
0

这种题目呢，因为是一开始做，就摸不着头脑，每次都是看了别人的解析才恍然大悟，不过呢，看懂了自己也打出来了也算好事一件吧。照猫画虎，按照自己的理解把解题过程打出来吧，也算再梳理思路。

思路

第一次思路

首先拿到题目，我们应该先用常规思路想一下，自己会怎么做。因为子串的次序是严格递增的，所以我们把x串作为主串，y串作为第二串，将主串里每个字符依次与第二串的进行比较，找到匹配的，直到第二串结束。
如果出现重复的字符，我们不知道是选择第一次遇到的还是后面的，因为导致的公共子序列长度不一定，那是一一列出来吗？这差不多就是穷举法，时间复杂度很高。

动态规划思路

• 分析最优解的性质，并刻画其结构特征

我们尝试用动态规划的思想去分解这个问题。如果将大问题分解成小问题呢？我们发现，如果x序列的末尾和y序列的末尾一致，那最长公共子序列的最后一个必然是x序列的末尾。
如abc和ac，c必然是最长公共子序列的最后一个，接下来就看除去c后的最长公共子序列是什么了。
所以我们似乎发现了一些规律：（令x序列长度m，y序列长度n，最长公共子序列为z，长度为k）

if Xm==Yn:
  Zk=Xm

那么k就是Xm-1与Ym-1的最长公共子序列长度再加1。
如果xm！=yn，假设Zk!=Xm，那么把Xm拿走，Zk仍旧是Xm-1和Yn的最长公共子序列。
所以当xm！=yn时，就比较Xm-1和Yn的最长公共子序列和Xm和Yn-1的最长公共子序列哪个长，即为最长。

• 递归的定义最优解

令dp[i][j]存放Xi和Yi的最长公共子序列长度。
有：
Xm==Yn时 dp[i][j]=dp[i-1][j-1]+1
Xm!=Yn时 dp[i][j]=max{dp[i-1][j],dp[i][j-1]}

• 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值

动态规划是自底向上解决问题的，最后就解决了大问题。
如abc和ac，求dp[3][2]，是第一种情况，需要求dp[2][1]，那dp[2][1]怎么求呢？
我们可以从解决dp[1][1]开始一步步来，这样后面的解就可以利用前面的得出。

 for(int i = 1; i < xmax+1; i++)
    {
        for(int j = 1; j < ymax+1; j++)
        {
            if(x.at(i-1)==y.at(j-1))  //情况1
                dp[i][j]=dp[i-1][j-1]+1;
            else //情况2
                dp[i][j]=(dp[i-1][j]>dp[i][j-1])?dp[i-1][j]:dp[i][j-1];
        }
    }

• 根据计算最优值时得到的信息，构造问题的最优解
  之前是建表，现在就直接把x和y的长度带进去查表，就知道最优解了
  int answer=dp[xmax][ymax];

代码

请看下面链接

本文参考自：放下梧菲的文章