POJ1159

POJ1159是一个动态规划问题，也被称为“Palindrome”。题目描述如下：

给定一个字符串，你需要将它分割成若干个子串，使得每个子串都是回文串。求最少需要分割几次。

例如，对于字符串“abcbm”，最少需要分割一次，将它分割成“a”、“bcb”和“m”三个回文子串。

解题思路：

使用动态规划求解。定义dp[i]为字符串s的前i个字符最少需要分割几次才能满足条件。则有如下状态转移方程：

dp[i] = min(dp[j]) + 1，其中j<i且s[j+1:i]是回文串

即在前i个字符中找到一个位置j，使得s[j+1:i]是回文串，且dp[j]是前j个字符最少需要分割几次才能满足条件，那么dp[i]就可以通过dp[j]得到。

时间复杂度为O(n^2)。具体实现细节见下面的代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n;
char s[N];
int dp[N];

bool check(int l, int r)
{
    while (l < r)
    {
        if (s[l] != s[r])
            return false;
        l++;
        r--;
    }
    return true;
}

int main()
{
    cin >> n >> s + 1;

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (check(j + 1, i))
                dp[i] = min(dp[i], dp[j] + 1);

    cout << dp[n] - 1 << endl;

    return 0;
}