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.
这种求最优解的问题就不适合用dfs做了，最优解一般都是DP，比遍历所有情况比较快。
这道题的dp很好想，就是i之前的最优解=min（j之前的最优解+1） j<i。
但是这么做还是不能通过测试，原因是，之前做的palindrome的检查是将字串反过来，如果和原来的字串相同，说明他是palindrome。
检查是否是palindrome也可以用dp来解决。isPalindrome（j， i）= string(j) == string(i) && isPalindrome（j+1，i-1）;
1 public static int minCut(String s) { 2 boolean[][] table = new boolean[s.length()+1][s.length()+1]; 3 for (int i=0; i<table.length; i++) table[i][i] = true; 4 int[] result = new int[s.length()+1]; 5 result[0] = -1; 6 for (int i=1; i<=s.length(); i++) { 7 int min = Integer.MAX_VALUE; 8 for (int j = 0; j<i; j++) { 9 if (isPalindrome(s, j, i, table)) { 10 if (min > result[j] + 1) min = result[j]+1; 11 } 12 } 13 result[i] = min; 14 } 15 return result[s.length()]; 16 17 } 18 19 20 public static boolean isPalindrome(String s, int start, int end, boolean[][] table) { 21 if (end - start == 1) { 22 table[start][end] = true; 23 } 24 else if (s.charAt(start) == s.charAt(end-1) && table[start+1][end-1]) { 25 table[start][end] = true; 26 } 27 else { 28 table[start][end] = false; 29 } 30 return table[start][end]; 31 }