UVA11584 简单DP优化

题意

给出N个字符串，分别求出这N个字符串最少可以分割成多少个回文子串。

题解

设dp[i]为1-i个字符最少可以分割成的回文串个数，可得状态转移方程为dp[i]=min(dp[j]+1,dp[i])（I到J为回文串）。但是，在这种情况下，时间复杂度会达到O(N^3)，所以我们需要对程序进行优化。优化方式为将从I到J是否为回文串的判断进行预处理，针对每一个字符I，判断该字符加上两边的字符，分别能组成哪些回文串。经过预处理，可将时间复杂度降低到O(N^2)。

注意事项

注意初始化dp[0]=0

代码

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 1e9

using namespace std;
char ch[];
int dp[];
int re[][];

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",ch);
        int len=strlen(ch);
        for(int i=len;i>;i--){
            ch[i]=ch[i-];
        }
        ch[]=' ';
        for(int i=;i<=len;i++){
            dp[i]=i;
        }
        memset(re,,sizeof(re));

        //预处理回文串
        for(int i=;i<=len;i++){
            re[i][i]=;
            if(ch[i-]==ch[i+]){
                for(int j=;j<=len;j++){
                    if(i-j<||i+j>len)
                        break;
                    if(ch[i-j]==ch[i+j]){
                        re[i-j][i+j]=;
                        re[i+j][i-j]=;
                    }else{
                        break;
                    }
                }
            }
            if(ch[i-]==ch[i]){
                for(int j=;j<=len;j++){
                    if(i-j-<||i+j>len)
                        break;
                    if(ch[i--j]==ch[i+j]){
                        re[i-j-][i+j]=;
                        re[i+j][i-j-]=;
                    }else{
                        break;
                    }
                }
            }
            if(ch[i]==ch[i+]){
                for(int j=;j<=len;j++){
                    if(i-j<||i+j+>len)
                        break;
                    if(ch[i-j]==ch[i+j+]){
                        re[i-j][i+j+]=;
                        re[i+j+][i-j]=;
                    }else{
                        break;
                    }
                }
            }
        }

        dp[]=;
        for(int i=;i<=len;i++){
            for(int j=;j<len;j++){
                if(j<=i){
                    if(re[j+][i]){
                        //printf("%d %d %d\n",i,j+1,dp[j]);
                        dp[i]=min(dp[j]+,dp[i]);
                    }
                }

            }
        }
        printf("%d\n",dp[len]);
    }
    return ;
}