题目：
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.
思路：
题目要求将s划分为各个回文串找到最少的划分次数。则可以使用动态规划思想求解。
方法一：
使用二维数组w[i][j]记录从s[i]到s[j]之间的最少划分方法，则w[i][j] = min(w[i][k]+w[k+1][j]+1)其中i<=k<j，即当s[i]到s[j]这个整体不是回文的时候，要求k在i和j之间遍历，寻找最小的分割次数,并且i到k，k+1到j两子串必须都为回文串；若整体就是回文的，则w[i][j]就是0。最终得到w[0][n-1]即为所求值。
方法二：
使用一维数组d[i]专门记录从0到i这个子串的最少分割次数。则，d[i] = min(1+d[j]),其中0<=j<i;仍然需要使用j遍历0到i之间的分割点。但是其中的j是小于i的，也就是说，
d[i]所依赖的d[j]是已经计算出来的。并且需要判断j到i之间的子串是否是回文。如果不是则跳过当前j，进入下一个j的计算。
判断回文：
如果每次都将子串进行头尾相比然后向中心汇聚的方法，则速度太慢，重复性太强。因此使用p[i][j]来记录i到j之间的回文情况true or false。
在思考本题时，想到了p的赋值顺序是不是跟d的得出顺序相符。如果d[i]所依赖的某个p还从未计算过，那么结果一定是有问题的。
在下面证明了，d[i] 所使用到的任何一个p，都在d[i]之前的步骤中得出。
假设i=5；则
----------------------------
0， j 5
0,0->1,5=>需要2,4；3,3.在上一步已经得出。
0,1->2,5=>需要3,4；在上一步已经得出。
0,2->3,5；p[3[5]得出
0,3->4,5；p[4][5]得出
0,4->5,5；p[5[5]得出
----------------------------
0， j 4
0,0->1,4=>需要2,3；在上一步已经得出。
0,1->2,4=>需要3,3；在上一步已经得出。
0,2->3,4；p[3[4]得出
0,3->4,4；p[4[4]得出
----------------------------
0， j 3
0,0->1,3=>需要2,2.,在上一步已经得出。
0,1->2,3;p[2][3]得出
0,2->3,3;p[3][3]得出
----------------------------
0， j 2
0,0->1,2；p[1][2]得出
0,1->2,2；p[2][2]得出
----------------------------
0， j 1
0,0->1,1；p[1][1]得出
从下往上依次执行。
本题中使用到了两个动态规划，一个针对回文数判断，一个针对中间子串的分割点进行判断。题目不难，但很灵活。
AC代码（方法二）：
public class Palindrome_Partitioning_II {
private boolean judge(int i, int j, char[] strs, boolean[][] p) {
if (strs[j] == strs[i] && (j - i < 2 || p[i + 1][j - 1]))
p[i][j] = true;
else
p[i][j] = false;
return p[i][j];
}
public int minCut(String s) {
if (s.length() == 0)
return 0;
char[] strs = s.toCharArray();
int[] w = new int[strs.length];//for the times to seprate
boolean[][] p = new boolean[strs.length][strs.length];//for the palindrome judge.
for (int i = 0; i < w.length; i++) {
p[i][i] = true;
w[i] = i;
}
for (int i = 1; i < w.length; i++) {
if (judge(0, i, strs, p)) {
p[0][i] = true;
w[i] = 0;
} else
for (int j = 0; j < i; j++) {
if (judge(j + 1, i, strs, p)) {
w[i] = Math.min(w[i], 1 + w[j]);
}
}
}
return w[w.length - 1];
}
}