回文子串划分（基础DP）- UVA 11584

今天带来一个简单的线性结构上的DP，与上次的照明系统（UVA11400）是同一种类型题，便于大家类比、总结、理解，但难度上降低了。

We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not. A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups. Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome!

正序倒序写都相同的字符串我们称之为回文串。例如，‘racecar’就是回文的，‘fastcar’就不是。对一个字符序列的划分即：分成一堆（至少一个）非空不相交的连续字符串，使它们连起来就是原来的字符序列。例如，‘race’，‘car’就是把‘racecar’划分成两组。给定一个字符串，我们总能找到一种划分使得每个子串都是回文串！（大不了一个字母算一个子串）

Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome? For example:

• ‘racecar’ is already a palindrome, therefore it can be partitioned into one group.

• ‘fastcar’ does not contain any non-trivial palindromes, so it must be partitioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’).

• ‘aaadbccb’ can be partitioned as (‘aaa’, ‘d’, ‘bccb’).

求：使得每个子串都是回文串的最小划分组数。

例如，‘racecar’本身就是个回文串所以它的答案是1组；‘fastcar’不含回文子串，只能一个字母一个字母地分，答案为7组；‘aaadbccb’最优可以分成‘aaa’，‘d’，‘bccb’3组。

Input Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within..

最先输入测试组数n。每组给出一个长度1~1000的小写字母串，中间没有空格。

Output For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.

对于每组测试，输出可划分的最少组数。

Sample Input 3

racecar

fastcar

aaadbccb

Sample Output 1

7

3

思路：

假如我遍历一遍字符串 ----> 强如‘fastcar’的话只能一个字母一个字母地苦逼+1，那么有回文子串时，差异是如何产生的呢？ ----> 就说racecar吧。走到race的时候还是+1模式，再走一步到c的时候发现跟前面的ce能凑个cec ----> 我们用dp数组表示结果，dp[racec]本来等于dp[race]+1,由于找到了回文子串cec，所以变成了min（ dp[race]+1, dp[ra]+1 ） ----> 由于我们不知道当前字母最早可以伸展到哪里去跟别人结合为回文子串，所以可以暴力扫一遍前面的 ----> 至于回文串，一边扫一遍判断也可以，预处理也可以，关键是复杂度。预处理可以枚举回文串中心然后向左右伸展得到（j，i）是不是回文串，可以以n²的复杂度求解，这样dp的过程也是n²。一边dp一边判断大概是n³的复杂度，我不知道怎么就过了我复杂度算错了？……

最开始瞎写的代码1：20ms

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int T;
int dp[1001];
char str[1001];

bool ispalindrome(int start, int end)
{
    for (int i = start; i < (start+end+1)/2; i++)
        if (str[i] != str[start+end-i])
            return false;
    return true;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str+1);

        int len = strlen(str+1);
        for (int i = 1; i <= len; i++)
        {
            dp[i] = dp[i-1] + 1;
            for (int j = 1; j <= i-1; j++)
                if (ispalindrome(j, i))//[j,i]是不是回文
                    dp[i] = min(dp[i], dp[j-1] + 1);
        }

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

按照上面瞎改的代码2：20ms

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int T;
int dp[1001];
char str[1001];
bool ispalindrome[1001][1001];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str+1);

        int len = strlen(str+1);
        memset(ispalindrome, false, sizeof(ispalindrome));
        memset(dp, 0x3f, sizeof(dp));
        //预处理
        for (int i = 1; i <= len; i++)
        {
            for (int l = i, r = i; str[l] == str[r] && l >= 1 && r <= len; l--, r++)
                ispalindrome[l][r] = true;
            for (int l = i, r = i+1; str[l] == str[r] && l >= 1 && r <= len; l--, r++)
                ispalindrome[l][r] = true;
        }
        //dp
        dp[0] = 0;
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= i; j++)
                if (ispalindrome[j][i])//[j,i]是不是回文
                    dp[i] = min(dp[i], dp[j-1] + 1);

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