回文串问题。给出一个字符串，问最少可以划分为多少个字符串子串。
对于判断是否为回文串，对于不是很长的字符串，可以采取直接暴力，即从两边向中间收缩判断字符相等。
bool is_pali(int l, int r)
{
while(l < r)
{
if(str[l] != str[r]) return false;
++l; --r;
}
return true;
}
本题为简化复杂度，可以先预处理str[j...i]是否为回文串。
设dp[i]表示以第i个字符结尾的子串最少可以划分的回文串数。
则dp[i] = min{dp[i], dp[j-1]+1}; (j <= i && str[j...i]是回文串)；
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char str[];
int dp[];
bool is_pali(int l, int r)
{
while(l < r)
{
if(str[l] != str[r]) return false;
++l; --r;
}
return true;
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%s", str+);
int l = strlen(str+);
memset(dp, , sizeof(dp)); //dp[i]:以i结尾的串最少可以划分的回文串数
for(int i = ; i <= l; i++)
{
dp[i] = i; //最多可以划分为i+1个
for(int j = ; j <= i; j++)
{
if(is_pali(j, i))
dp[i] = min(dp[i], dp[j-]+); //此处避免下标越界
}
}
cout << dp[l] << endl;
}
return ;
}