POJ 1458 最长公共子序列(dp)

POJ 1458 最长公共子序列

题目大意：给出两个字符串，求出这样的一 个最长的公共子序列的长度：子序列 中的每个字符都能在两个原串中找到， 而且每个字符的先后顺序和原串中的 先后顺序一致。 

Sample Input ：

abcfbc abfcab

programming contest

abcd mnp

Sample Output

4 2 0

分析：

输入两个串s1,s2, 设dp(i,j)表示: s1的左边i个字符形成的子串，与s2左边的j个 字符形成的子串的最长公共子序列的长度(i,j从0 开始算） dp(i,j) 就是本题的“状态”。

假定 len1 = strlen(s1),len2 = strlen(s2） 那么题目就是要求 MaxLen(len1,len2)

递推公式： if ( s1[i-1] == s2[j-1] ) dp(i,j) = dp(i-1,j-1) + 1; else dp(i,j) = Max(dp(i,j-1),dp(i-1,j) );

时间复杂度O(mn) m,n是两个字串长度

代码：

#include<iostream>
#include<cstring>
using namespace std;
#define N 1000
char str1[N];
char str2[N];
int dp[N][N];
int main() {
    while(cin >> str1 >> str2) {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        for(int i = 0; i < len1; i++) dp[i][0] = 0;
        for(int i = 0; i < len2; i++) dp[0][i] = 0;
        for(int i = 0; i < len1; i++) {
            for(int j = 0; j < len2; j++) {
                if(str1[i] == str2[j]) 
                    dp[i+1][j+1] = dp[i][j] + 1;
                else {
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
                } 
            }
        }
        cout << dp[len1][len2] << endl;
    }
    return 0;
}