有一个字符串S，求S最少可以被划分为多少个回文串。
例如：abbaabaa，有多种划分方式。
a|bb|aabaa - 3 个回文串
a|bb|a|aba|a - 5 个回文串
a|b|b|a|a|b|a|a - 8 个回文串
其中第1种划分方式的划分数量最少。
Input
输入字符串S(S的长度<= 5000)。
Output
输出最少的划分数量。
Input示例
abbaabaa
Output示例
3
题解
设dp[i]为考虑（i~len）的最少分割，那么
\(dp[i]=min(dp[i],dp[j+1]+1)\;if(i,j)为回文串\)
这个可以倒推也可以正推，至于求回文串
if a[i]==a[j] and (i-1,j+1)是回文串
then (i,j)是回文串，这个是\(O(n^2)\)，与dp方程同级，就放在一起转移吧。
参考代码
import java.io.*;
import java.util.*;
public class Main {
static final int N=(int)5005;
static int dp[]=new int[N];
static char a[]=new char[N];
static boolean p[][]=new boolean[N][N];
public static void main(String[] args) {
InputStream sys=System.in;
InputReader in=new InputReader(sys);
PrintWriter out=new PrintWriter(System.out);
a=in.next().toCharArray();
dp[a.length]=0;
for(int i=a.length-1;i>=0;i--) {
dp[i]=Integer.MAX_VALUE;
for(int j=i;j<=a.length-1;j++) {
if(a[i]==a[j]&&(j-i<2||p[i+1][j-1])) {
p[i][j]=true;
dp[i]=Math.min(dp[i], dp[j+1]+1);
}
}
}
out.println(dp[0]);
out.flush();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}