最长公共子序列(Longest Common Subsequence,LCS)

　　对于一个字符串而言：

　　字串是指在该字符串中取出连续的一块

　　子序列是指在该字符串中删去若干元素后得到的序列

　　给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列是长度最长的子序列。

　　LCS问题：给定两个序列X和Y，找出X和Y的一个最长公共子序列。

一：当X_i=Y_j时，找出X_i-1=Y_j-1的最长公共子序列，然后在其尾部加上X_i即可得到X和Y的最长公共子序列。

二：当X_i≠Y_j时，

　　1.找到X_i-1和Y_j的最长公共子序列。

　　2.找到X_i和Y_j-1的最长公共子序列。

　　3.取两者最大值。

练习：hdu1159：http://acm.hdu.edu.cn/showproblem.php?pid=1159

代码如下：

#include <bits/stdc++.h>
using namespace std;
string str1;
string str2;
int dp[1005][1005];
int main(int argc, char const *argv[])
{
    while(cin>>str1>>str2)
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1; i <= str1.length(); ++i)
        {
            for (int j = 1; j <= str2.length(); ++j)
            {
                if (str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
        cout<<dp[str1.length()][str2.length()]<<endl;
    }
    return 0;
}