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. 这道题跟非常类似，区别就是不需要返回所有满足条件的结果，而只是返回最小的切割数量就可以。做过的朋友可能马上就会想到，其实两个问题非常类似，当我们要返回所有结果（和）的时候，使用动态规划会耗费大量的空间来存储中间结果，所以没有明显的优势。而当题目要求是返回某个简单量（比如是返回能否切割，而这道题是返回最小切割数）时，那么动态规划比起brute force就会有明显的优势。这道题先用中的方法建立字典，接下来动态规划的方式和是完全一样的，我们就不再细说了，不熟悉的朋友可以看看的分析哈。因为保存历史信息只需要常量时间就能完成，进行两层循环，时间复杂度是O(n^2)。空间上需要一个线性数组来保存信息，所以是O(n)。
第二遍做法：比第一遍稍改进一点
关于14行：if dic[0][i-1] 说明0到i-1就是回文，mincut=0
1 public class Solution { 2 boolean[][] dic; 3 public int minCut(String s) { 4 if (s==null || s.length()==0) return 0; 5 dic = new boolean[s.length()][s.length()]; 6 getDict(s); 7 int[] dp = new int[s.length()+1]; 8 dp[0] = 0; 9 dp[1] = 0;10 for (int i=2; i<=s.length(); i++) {11 dp[i] = i-1;12 for (int j=0; j<=i-1; j++) {13 if (dic[j][i-1]) {14 dp[i] = Math.min(dp[i], j==0? 0 : dp[j]+1);15 }16 }17 }18 return dp[s.length()];19 }20 21 public void getDict(String s) {22 for (int i=s.length()-1; i>=0; i--) {23 for (int j=i; j
第一遍过得时候的做法：res[k]的意思是：string前k个元素组成的substring的最小cut数，res[0]=0, res[1]=0, 其它index初始化为res[k] = k-1。因为前k个元素最多需要k-1个cut就能确保每个substring是回文（每个都只有一个字符），然后迭代开始，递归表达式为if dict[0][i-1]为真，res[i]=0; else if dict[j][i-1]为真，res[i] = Math.min(res[i], res[j]+1)
1 public class Solution { 2 public int minCut(String s) { 3 if (s==null || s.length()==0 || s.length()==1) return 0; 4 boolean[][] dict = getdict(s); 5 int[] res = new int[s.length()+1]; 6 res[0] = 0; 7 res[1] = 0; 8 for (int k=2; k<=s.length(); k++) { 9 res[k] = k-1;10 }11 for (int i=2; i<=s.length(); i++) {12 for (int j=0; j =0; i--) {25 for (int j=i; j