入坑动态规划！POJ 1458字符串最大公共子序列

题干大概： 寻找两字符串最大公共子序列

我是看了北大在coursera的网课，过来做这道题的，一开始我用递归试了一下；

int maxlen(int len1,int len2){
     if(len1==0 || len2==0) return 0;
     if(s1[len1-1]==s2[len2-1]) return maxlen(len1-1,len2-1)+1;
     else return max(maxlen(len1-1,len2),maxlen(len1,len2-1));
}

妥妥的，没过，然后我就想如何把递归改成递推。

想了想，没想出来，但我想到一个其他歪办法：

从0位置比较两字符串，字符相同的话ans++，i1++,i2++,不相同的话初始turn_s1=true，turn_s1为真时，i1++，为假时i2++，turn_s1=false.

怎么样，很妙吧

妙个鬼...比如说，这个就过不了

s1="21.",s2=".21",结果显示就是1...

在我的印象里，动归似乎是一种非常奇妙的魔法（算法），可以用很简单的步骤解决问题；

但是其实，动归也不过是一种遍历的策略；

再牛逼的算法，对于这道题也不能够做到不完全遍历两个字符串就给出答案，你说是不是大兄弟。

这是答案，是很妙的答案，也是最原始最暴利的答案：

#include<iostream>
#include<string.h>
using namespace std;

const int maxn=1000+20;
int maxlen[maxn][maxn];

int main(){
	int i1,i2; 
	char s1[maxn],s2[maxn];
	while(scanf("%s%s",s1,s2)==2){
                i1=i2=0;
		int l1=strlen(s1);
		int l2=strlen(s2);
		for(int i=0;i<=l1;i++) maxlen[0][i]=0;       //赋值
		for(int i=0;i<=l2;i++) maxlen[i][0]=0;       //赋值

		for(int i=1;i<=l1;i++){                      //递推，和上文中的递归逻辑差不多
			for(int l=1;l<=l2;l++){
			if(s1[i-1]==s2[l-1]){maxlen[i][l]=maxlen[i-1][l-1]+1;continue;}     //如果有相等的，直列下一轮
			maxlen[i][l]=max(maxlen[i-1][l],maxlen[i][l-1]);                    //说明没有相等，max一下
		}
                }
		cout<<maxlen[l1][l2]<<endl;
	}
    return 0;
}


最后我用记忆递归试了一下，发现不但能过，还比上面的快，mmp..

#include<iostream>
#include<string.h>
using namespace std;

const int maxn=1000+20;
int maxlen[maxn][maxn];

int main(){
    int i1,i2; 
    char s1[maxn],s2[maxn];
    while(scanf("%s%s",s1,s2)==2){
        i1=0;i2=0;
        int l1=strlen(s1);
        int l2=strlen(s2);
        for(int i=0;i<=l1;i++) maxlen[0][i]=0;
        for(int i=0;i<=l2;i++) maxlen[i][0]=0;
        for(int i=1;i<=l1;i++){
            for(int l=1;l<=l2;l++)
        {
            if(s1[i-1]==s2[l-1]) {
            maxlen[i][l]=maxlen[i-1][l-1]+1;continue;}
            maxlen[i][l]=max(maxlen[i-1][l],maxlen[i][l-1]);
        }}
        cout<<maxlen[l1][l2]<<endl;
    }
    return 0;
}