dp专题-UVA - 11584 划分回文串-O(n^2)处理子串是否为回文串

题目链接：https://vjudge.net/contest/306591#problem/G
题目大意：
意思就是：把一个字符串进行划分，要求每个子串为回文串，并且要求划分之后总的回文子串最少。

dp其实很好想：dp[i]表示：以i为结尾划分的最少的回文数量。
那么:dp[i]=min(dp[i], dp[j]+[j+1, i]为回文?1:0);(j<i)

但是要频繁判断子串是否为回文。Manacher也要O(n^3)的复杂度。
这里我想到了dp预处理的思路：
vis[i][j]表示为回文,那么如果：(a[i]==a[j])&&vis[j+1][i-1] 那么vis[i][j]=1

vis[j+1][i-1]为长度，那么我们以长度为第一维进行dp。在O(n^2)时间内全部预处理完：s[j]-s[i]是否为回文。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

char s[1050];
int vis[1010][1010];
int dp[1010];

int dfs(int L ,int R)
{
    if(L>R)
    {
        return 1;
    }
    else
    {
        return vis[L][R];
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s+1);
        int n=strlen(s+1);
        memset(vis, 0, sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            vis[i][i]=1;
            dp[i]=i;
        }
        
        //dp回文字符串
        for(int Len=2;Len<=n;Len++)
        {
            for(int i=Len;i<=n;i++)
            {
                if(dfs(i-Len+2, i-1)&&s[i]==s[i-Len+1])
                {
                    vis[i-Len+1][i]=1;
                }
            }
        }
        
        //dp最少的划分数
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(dfs(j+1, i))
                {
                    dp[i]=min(dp[i], dp[j]+1);
                }
            }
        }

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

    return 0;
}