动态规划-最长公共子序列(POJ1458)

可以参考: http://m.blog.csdn.net/hrn1216/article/details/51534607

给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先先后顺序和原串中的先后顺序一致.

输入

abcfbc abfcab
programming contest
abcd mnp

输出

4
2
0

输入两个串s1,s2,设MaxLen(i,j)表示:s1的左边i个字符形成的子串,与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j)从0开始算
MaxLen(i,j)就是本题的"状态"
假定len1 = strlen(s1),len2 = strlen(s2)
那么题目就是要求MaxLen(len1,len2)

#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];

int main()
{
    while(cin>>sz1>>sz2){
        int length1 = strlen(sz1);
        int length2 = strlen(sz2);
        for(int i=0;i<length1;i++)
            maxLen[i][0] = 0;
        for(int j=0;j<length2;j++)
            maxLen[0][j] = 0;
        for(int i=1;i<=length1;i++){    //此时是数组下标,不能从0开始
            for(int j=1;j<=length2;j++)
                if(sz1[i-1] == sz2[j-1])
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                else
                    maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
        }
        cout<<maxLen[length1][length2]<< endl;
    }

    return 0;
}