动态规划 POJ-1458 Common Subsequence

题目链接：[ POJ - 1458 ]

题目大意

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

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

思路

显然: MaxLen(n,0) = 0 ( n= 0...len1) MaxLen(0,n) = 0 ( n=0...len2)
递推公式:

 if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]  
    MaxLen(i,j) = MaxLen(i-1,j-1) + 1;  
 else  
    MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );  

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

题解代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
int dp[maxn][maxn];
char a[maxn], b[maxn];

int main(void)
{
    while (cin >> a >> b) {
        memset(dp, 0, sizeof(dp));
        int len1 = strlen(a);
        int len2 = strlen(b);
        for(int i = 0; i < len1; i++) {
            for(int j = 0; j < len2; j++) {
                if(a[i] == b[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;
}