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.
难度：90. 这道题跟Palindrome Partitioning非常类似，区别就是不需要返回所有满足条件的结果，而只是返回最小的切割数量就可以。做过Word Break的朋友可能马上就会想到，其实两个问题非常类似，当我们要返回所有结果（Palindrome Partitioning和Word Break II）的时候，使用动态规划会耗费大量的空间来存储中间结果，所以没有明显的优势。而当题目要求是返回某个简单量（比如Word Break是返回能否切割，而这道题是返回最小切割数）时，那么动态规划比起brute force就会有明显的优势。这道题先用Palindrome Partitioning中的方法建立字典，接下来动态规划的方式和Word Break是完全一样的，我们就不再细说了，不熟悉的朋友可以看看Word Break的分析哈。因为保存历史信息只需要常量时间就能完成，进行两层循环，时间复杂度是O(n^2)。空间上需要一个线性数组来保存信息，所以是O(n)。
第二遍做法：比第一遍稍改进一点
关于14行：if dic[0][i-1] 说明0到i-1就是回文，mincut=0
public class Solution {
boolean[][] dic;
public int minCut(String s) {
if (s==null || s.length()==0) return 0;
dic = new boolean[s.length()][s.length()];
getDict(s);
int[] dp = new int[s.length()+1];
dp[0] = 0;
dp[1] = 0;
for (int i=2; i<=s.length(); i++) {
dp[i] = i-1;
for (int j=0; j<=i-1; j++) {
if (dic[j][i-1]) {
dp[i] = Math.min(dp[i], j==0? 0 : dp[j]+1);
}
}
}
return dp[s.length()];
}
public void getDict(String s) {
for (int i=s.length()-1; i>=0; i--) {
for (int j=i; j<s.length(); j++) {
if (s.charAt(i)==s.charAt(j) && (j-i<=2 || dic[i+1][j-1]))
dic[i][j] = true;
}
}
}
}