1.最长公共子序列的定义：
我们称序列Z=<z1,z2,...,zk>，Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>X=<x1,x2,...,xm>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik><i1,i2,...,ik>，使得对j=1,2,...,k,有xij=zjxij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
没搞懂？举个例子：
abcfbc abfcab 两序列最长公共子序列长度为4，最长公共子序列为：abfc
（别急，好好理解一下再往下看）

2.最长公共子序列的状态设计：
在解动态规划题目是，我们最重要的一步就是设计状态，一个状态设计的好坏直接关系到这道题你是否能够完美解出。我们回想一下LIS算法，那么我们现在是否也能够通过以一个数结尾的序列长度进行分析呢？我们就从这里入手，不难想到，在第一个串中以某个数结尾与在第二个串中以某个数结尾形成的最长公共子序列可以此题的作为状态，这样就可以将问题一步步化简，直到化简到某个（某些）特定的值便可通过它作为一个突破口解这道题。所以我们设f[i,j]为这题的状态，f[i,j]表示在第一个串的前个数字与在第二个串中前j个数字形成的最长公共子序列。

3.最长公共子序列的状态转移方程：
在状态设计时，我们讲到有某个特定的值在最长公共子序列中存在，这些特定的值就像递归函数的出口，那么这个值是什么呢？这个值往往是一个极端值或是一个与单个元素有关的值。没错，就是f[0,j]=0（即第一个串中的前0个数字和第二个串中的前j个数字形成的最长公共子序列长度为0）和f[i,0]（即第二个串中的前0个数字和第一个串中的前i个数字形成的最长公共子序列长度为0），这一定是没毛病的！
找到突破口之后，我们便要找到更一般的值，想找到这个值，那么我们想一下f[i,j]和什么有关呢？没错，就是就是与它自身有关（听起来有点....）
当第一个串中的第i个数字与第二个串中的第j个元素相等时，最长公共子序列的长度便是f[i-1,j-1]+1(这两个前面的最长公共子序列的长度+1)，那么当两个元素不等时呢?试想：第一个串中的前i-1个元素会不会与第二个串中的第j个元素相等呢，第二个串中的前j-1个元素会不会与第一个串中的前i个元素相等呢？这是很可能的。此时你可能要说了：为什么不比较f[i-2,j]&f[i,j-2]呢？问得好，因为我们是从前往后进行推导（i-1，i-2...都已经算出来了），并且要考虑较多的元素（前i-2个元素和前i-1个元素那个多呢？）
所以说，当两个元素不等时，我们就只考虑选择f[i-1,j]和f[i,j-1]中的较大的一个.

综上所述,状态转移方程为：
1.f[0,j]=0,f[i,0]=0
2.f[i-1,j-1]+1 //第一个串第i个元素和第二个串第j个元素相等时
3.max(f[i-1,j],f[i,j-1]) //第一个串第i个元素和第二个串第j个元素不等时

4.附打表模拟：
图片说明

5.代码：

#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a,b;
int c;
int f[1000][1000];
int main() {
    while(cin>>a>>b) {

        for(int i=1; i<=a.size(); i++) {
            for(int j=1; j<=b.size(); j++) {
                if(a[i-1]==b[j-1])
                    f[i][j]=f[i-1][j-1]+1;
                else
                    f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
        }
        for(int i=1; i<=a.size(); i++)
            for(int j=1; j<=b.size(); j++)
                c=max(c,f[i][j]);
        cout<<c<<endl;
        c=0;
        a.clear();
        b.clear();
        memset(f,0,sizeof(f));
    }


    return 0;
}

6.编写时注意事项：
1.由于f[0,j]=0,f[i,0]=0, so要开的数组是a.size()+1*b.size()+1的
2.写循环时，注意i与j的初始值要设为1（12行），不仅是因为f[0,j],f[i,0]不需要走，还因为会越界（15行）
3.因为我们的循环没有从0开始走，而字符串存储是从下标为0的地方开始存储，所以在访问第一个元素时，要访问a[0]，之后以此类推，所以有了第14行的判断条件。