题意：
给定一个字符串s，将s分割成一些子串，使每个子串都是回文。
返回s符合要求的的最少分割次数。
样例：
比如，给出字符串s = "aab"，
返回 1， 因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串
1.n^3的解法(超时)
(1).解题思路
这道题最简单的解法，就是从头遍历，依次计算出每个字符的最小切割次数，动态规划的方程：dp[i] = Math.min(dp[j] + 1, dp[i])。不过这里需要注意的是，由于dp数组默认值是0，min求最小值的结果可能会受到这个默认值得影响，所以需要一定的过滤。
(2).代码
public int minCut(String s) {
int dp[] = new int[s.length() + 1];
Arrays.fill(dp, 0);
dp[1] = 1;
for (int i = 2; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
//dp[j] != 0,表示的意思就是：0~j是回文字符串
if ((dp[j] != 0 || j == 0) && check(s.substring(j, i))) {
//如果dp[i] 为0，表示dp[i]未被赋值
//这里是为了避免dp[i]为0的影响
if (dp[i] == 0) {
dp[i] = dp[j] + 1;
}
dp[i] = Math.min(dp[j] + 1, dp[i]);
}
}
}
System.out.println(Arrays.toString(dp));
return dp[s.length()] - 1;
}
/**
* 判断字符串是否为回文字符串
* @param string 判断的字符串
* @return
*/
public boolean check(String string) {
int length = string.length() / 2;
for (int i = 0; i < length; i++) {
if (string.charAt(i) != string.charAt(string.length() - 1 - i)) {
return false;
}
}
return true;
}
2.n^2的解法
n3 的解法有一个优势--空间复杂度只有O(n)。而n3的解法的空间复杂度是O(n2)。
(1).解题思路
第一步，创建一个二维数组，假设为b，其中b[i][j],表示的是如果i~j范围的字符串是回文字符串的话，b[i][j]为true，反之为false。这里就是这道题比较难的部分。
这里用图片来辅助解释一下
例如上面的图片，其中i在[1,s.length()]区间里面，至于为什么在这个区间里面，待会代码中解释；j再[0, s.length() - i + 1)区间里面；k是由i，j计算出来的。
从图中我们可以得出的是，i表示[i,k]的字符串的中心，i，表示子串的两端，我们可以得出：如果s.charAr(j) == s.charAt(k)和b[j +1][k - 1]为true的话，b[i][k]肯定为true。
第二步，再创建一个以维数组，假设为dp,其中dp[i],表示切割0~i范围的字符串的最小次数。动态规划方程：dp[i] = Math.min(dp[i], dp[j] + 1);
(2).代码
public int minCut(String s) {
boolean[][] b = new boolean[s.length()][s.length()];
for (int i = 1; i <= s.length(); i++) {
//j表示以i为中心的子字符串左侧
//s.length() - i + 1,计算的是i的右侧还有几个字符
//所以j在[0, s.length() - i + 1)
//这里便能解释为什么i必须从1开始，如果从0开始的话，0是没有左侧的
for (int j = 0; j < s.length() - i + 1; j++) {
//以i为中心，与j对应的右侧位置k
int k = j + i - 1;
if (i == 1) {
b[j][k] = true;
} else {
if (s.charAt(j) == s.charAt(k) && (j == k - 1 || b[j + 1][k - 1]))
b[j][k] = true;
}
}
}
int[] dp = new int[s.length()];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < s.length(); i++) {
if (b[0][i]) {
dp[i] = 0;
}
for (int j = 0; j < i; j++) {
if (b[j + 1][i])
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
return dp[s.length() - 1];
}
