Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
题意：一个字符串，求把它分割成回文串组合的最小分割次数。
思路：
动态规划解法。对于字符串str，用cut[i]表示从0到i的最短分割次数，用isPalind[j][k]表示从j到k是否是一个回文串。对于0..i..k，i可以是对于从0到k的任意位置，i大于0时，只要i到k是回文，就可以求出一个对于0到k的分割次数，即cut[i-1] + 1，则cut[k]是所有这些次数的最小值；如果i等于0，并且i到k就是回文，则cut[k] = 0。
public int minCut(String s) {
if (s == null || s.length() <= 1) {
return 0;
}
int len = s.length();
int[] minCutNum = new int[len];
boolean[][] isPalind = new boolean[len][len];
for (int i = 0; i < len; i++) {
int min = i;
for (int j = 0; j <= i; j++) {
if (s.charAt(j) == s.charAt(i) && (i - j < 2 || isPalind[j+1][i-1])) {
if (j == 0) {
min = 0;
} else {
min = Math.min(min, minCutNum[j-1] + 1);
}
}
}
minCutNum[i] = min;
}
return minCutNum[len - 1];
}