POJ1159 Palindrome(dp)

分析：

感叹算法的力量。

方法一：

设 dp[i][j] 为字符串 s, 从 i 到 j 需要添加的最少字符数。

那么如果 s[i] == s[j], dp[i][j] = dp[i+1][j-1]. 如果 s[i] != s[j], dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1.

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <map>

using namespace std;

const int maxn = ;

short dp[maxn][maxn];

char s[maxn];

int d(int i, int j) {

    if(i >= j) return ;

    else if(dp[i][j] != -) return dp[i][j];

    else if(s[i] != s[j]) return (dp[i][j] = min(d(i+, j), d(i, j-)) + );

    else return dp[i][j] = d(i+, j-);

}

int main(){

  //  freopen("my.txt", "r", stdin);

    int n;

    while(scanf("%d", &n) == ) {

        memset(dp, -, sizeof(dp));

        scanf("%s", s);

        d(, n-);

        printf("%d\n", dp[][n-]);

    }

    return ;

}

方法二：

LCS + 滚动数组.

设原序列S的逆序列为S'，

最少需要补充的字母数 = 原序列S的长度 — S和S'的最长公共子串长度

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <map>

using namespace std;

const int maxn = +;

int dp[][maxn];

char s1[maxn], s2[maxn];

int main(){

    int n;

    while(scanf("%d", &n) == ) {

        scanf("%s", s1);

        memset(dp[], , sizeof(dp[]));

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

            s2[n-i-] = s1[i];

        }

        s2[n] = '\0';

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

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

                if(s1[i-] == s2[j-]) dp[i%][j] = dp[(i-)%][j-] + ;

                else dp[i%][j] = max(dp[(i-)%][j], dp[i%][j-]);

            }

        }

        printf("%d\n", n-dp[n%][n]);

    }

    return ;

}

巴特西

POJ1159 Palindrome(dp)

最新文章

热门文章