51nod 1154回文串划分 dp+递推

男娘i 2022-08-19 15:18 165阅读 0赞

题意：

有一个字符串S，求S最少可以被划分为多少个回文串。

例如：abbaabaa，有多种划分方式。

a|bb|aabaa - 3 个回文串

a|bb|a|aba|a - 5 个回文串

a|b|b|a|a|b|a|a - 8 个回文串

其中第1种划分方式的划分数量最少。

分析：

刚开始以为类似abab这样的字符串也是回文的，卡了好久，orz

dp\[i\]表示的是前i个字符组成的字符串的最少划分数量。

递推公式为：

dp\[i\] =min (dp\[i\] , dp\[j-1\]+1)   当j<=i并且字符j到i组成的字符串为回文的。

其中初始化为dp\[i\] = i ;

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 5005 ;
    int dp[maxn];//dp[i]表示的是以第i个字符结尾的最少划分数
    //dp[i] = min(dp[i],dp[j]+1)  当j到i是回文串时
    char str[maxn];
    bool vis[maxn][maxn] ; //vis[i][j]表示的是从i到j的字符串是否是回文串
    
    int main()
    {
        while(scanf("%s",str)!=EOF)
        {
            int n = strlen(str);
            memset(vis,0,sizeof(vis));
            //初始化
            for(int i = 0 ; i < n ; i++)
            {
                vis[i][i] = 1 ;
            }
            dp[0]=1;
            for(int i = 1 ; i < n ; i++)
            {
                dp[i] = i+1 ;
                dp[i] = min(dp[i] , dp[i-1]+1);
                
                //判断j到i是否是回文串
                for(int j = i-1 ; j >= 0 ; j--)
                {
                    if(j==i-1 && str[i]==str[j])
                    {
                        if(j-1>=0)dp[i] = min(dp[i] , dp[j-1]+1);
                        else dp[i] = 1 ;
                        vis[j][i]=1;
                    }
                    else if(vis[j+1][i-1]&&str[i]==str[j])
                    {
                        if(j-1>=0)dp[i] = min(dp[i] , dp[j-1]+1);
                        else dp[i] = 1 ;
                        vis[j][i]=1;
                    }
    
                }
            }
    //        for(int i = 0 ; i < n-1 ; i++)
    //        {
    //            printf("%d ",dp[i]);
    //        }
            printf("%d\n",dp[n-1]);
        }
        return 0;
    }