UVa11584Partitioning by Palindromes(字符串區間dp)

UVa11584Partitioning by Palindromes(字符串區間dp)

UVa11584Partitioning by Palindromes(字符串區間dp)

題意：給定一個字符串s, 問說最少可以劃分成幾個回文串。

思路：dp[i]表示從1到第i個字符最少可以劃分為幾個回文，狀態轉移方程

dp[i] = min(dp[i], dp[j-1]+1), 如果滿足 s[j] 到 s[i] 為回文字符串。

用 judge 函數判斷從j到i是否可以形成回文串。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double PI = acos(-1.0);
const double e = 2.718281828459;
const double eps = 1e-8;
const int MAXN = 1010;
char s[MAXN];
int dp[MAXN];

int judge(int l, int r)
{
    while(l <= r)
    {
        if(s[l] != s[r])
            return 0;
        l++;
        r--;
    }
    return 1;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int Case;
    cin>>Case;
    while(Case--)
    {
        scanf("%s", s+1);
        int len = strlen(s+1);
        dp[0] = 0;
        for(int i = 1; i <= len; i++)
            dp[i] = 1010;
        for(int i = 1; i <= len; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                if(judge(j, i))
                    dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
        cout<