题解 P1435 【回文字串】

d3ac · 2019-10-22 17:52:53 · 题解

设dp[i][j]表示i\to j成为回文字串的需要添加最少的字串数

• 枚举区间长度k和区间起点i，然后可以算出区间的终点j=i+k-1

• 当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

可是太浪费空间了，而且每次转移只会利用到dp[i+1][j]和dp[i][j-1]

• 所以就压维，还是枚举区间长度k和区间起点i
• 当s[i]=s[j]时， dp[i \ mod \ 2][j]=dp[(i+1) \ mod \ 2][j-1]
• 当s[i]!=s[j]时，dp[i \ mod \ 2][j]=min(dp[(i+1) \ mod \ 2][j],dp[i \ mod \ 2][j-1])+1

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int f[2][1200];
char s[1200];
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1),now=0;
    for(int i=len-1;i;i--){
        for(int j=i+1;j<=len;j++){
            if(s[i]==s[j]) f[now^1][j]=f[now][j-1];
            else f[now^1][j]=min(f[now][j],f[now^1][j-1])+1;
        }
        now^=1;
    }
    printf("%d\n",f[now][len]);
    return 0;
}