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 + ;

char str[maxn];

char sub[maxn];

int dp[][maxn];

void work() {

    int now = ;

    int lenstr = strlen(str + );

    int lensub = strlen(sub + );

    memset(dp, , sizeof dp);

    for (int i = ; i <= lenstr; ++i) {

        for (int j = ; j <= lensub; ++j) {

            if (str[i] == sub[j]) {

                dp[now][j] = dp[!now][j - ] + ;

            } else {

                dp[now][j] = max(dp[now][j - ], dp[!now][j]);

            }

        }

        now = !now;

    }

    cout << dp[!now][lensub] << endl;

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    IOS;

    while (cin >> str +  >> sub + ) work();

    return ;

}

巴特西

POJ 1458 Common Subsequence DP

最新文章

热门文章