POJ 1458 Common Subsequence DP

用dp[i][j]表示处理到第1个字符的第i个，第二个字符的第j个时的最长LCS。

1、如果str[i] == sub[j]，那么LCS长度就可以+1，是从dp[i - 1][j - 1] + 1，因为是同时捂住这两个相同的字符，看看前面的有多少匹配，+1后就是最大长度。

2、如果不同，那怎么办? 长度是肯定不能增加的了。

可以考虑下删除str[i] 就是dp[i - 1][j]是多少，因为可能i - 1匹配了第j个。也可能删除sub[j]，就是dp[i][j - 1]，因为可能str[i] == sub[j - 1]。同时考虑这两种情况的话，就是取max了。

因为只和上一维有关，所以可以用滚动数组来完成。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

const int maxn = 1e4 + 20;
char str[maxn];
char sub[maxn];
int dp[2][maxn];
void work() {
    int now = 0;
    int lenstr = strlen(str + 1);
    int lensub = strlen(sub + 1);
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= lenstr; ++i) {
        for (int j = 1; j <= lensub; ++j) {
            if (str[i] == sub[j]) {
                dp[now][j] = dp[!now][j - 1] + 1;
            } else {
                dp[now][j] = max(dp[now][j - 1], dp[!now][j]);
            }
        }
        now = !now;
    }
    cout << dp[!now][lensub] << endl;
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    IOS;
    while (cin >> str + 1 >> sub + 1) work();
    return 0;
}

POJ 1458 Common Subsequence DP

相关推荐