动态规划：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];
代码
请看下面链接
本文参考自：放下梧菲的文章
