最长公共子序列（动规）

动规的常用的两种形式：

1，递归型：

优点：直观，容易编写

缺点：可能会因为层数太深爆栈，调用函数带来额外的时间开销。无法使用滚动数组节省空间。总体来说，比递推型慢。

2，递推型：

效率高，有可能使用滚动数组节省空间。

（poj1458）

 现在就按着之前动规的思路来

 递推公式：

 这个递推公式还是简单的但是如果是不等的条件呢？

 这个的else就是这一题专有的条件了，这个地方就很难了。怎么证明这一点呢？只要证明左边这个不会比右边的两项都大，又不会比右边两项都小。

 这个要证明的话要使用反证法，首先很显然不会比两者其中一个小，因为字符都多出来了，肯定不可能会小，但是难的是为什么不会比两者都大呢？假设第一个比后面两个都大。MaxLen(s1,s2)比MaxLen(s1,s2j-1)多了一个s1[j-1]如果第一个比第二个大的话，说明s1[j-1]是要起作用的，不然是不会大的。同理s2[i-1]也是要起作用的。所以这两者肯定是位于最长公共子序列里面而且是最后一个字符。如果是这样的话就不满足s1[i-1] != s2[j-1].（说实话这个我自己思考完全搞不清楚）

 ×处的位置有两种途径来推，第一种是对角线（s1[i-1]和s2[j-1]相等）还有一种是上面或者左边的最大值。

#include 
#include 
#include 
using namesapce std;
char s1[1000];
char s2[1000];
int maxlen[1000][1000];
int main(){
    while(cin>>s1>>s2){
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        int Tmp;
        int i,j;
        for(i = 0;i<=len1;i++){
            maxlen[i][0] = 0;
        }
        for(j = 0;j<=len2;j++){
            maxlen[0][j] = 0;
        }
        for(i = 1;i<=len1;i++){
            for(j = 1;j<=len2;j++){
                if(s1[i-1] == s2[j-1]){
                    maxlen[i][j] = maxlen[i-1][j-1]+1;
                }else{
                    maxlen[i][j] = max(maxlen[i-1][j],maxlen[i][j-1]);
                }
            }
        }
        cout<endl;
    }