Palindrome Partitioning II

dynamic programming
 1 public class Solution {
 2     public static int minCut(String s) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if (s == null) {
 6             return 0;
 7         }
 8         int len = s.length();
 9         int[] cuts = new int[len];
10         for (int i = len - 1; i >= 0; i--) {
11             String str = s.substring(i);
12             if (isPalindrome(str)) {
13                 cuts[i] = 0;
14             } else {
15                 cuts[i] = getMin(s, i, len, cuts);
16             }
17         }
18         return cuts[0];
19     }
20 
21     public static int getMin(String s, int i, int len, int[] cuts) {
22         int min = Integer.MAX_VALUE;
23         for (int j = i + 1; j < len; j++) {
24             if (cuts[j] < min && isPalindrome(s.substring(i, j))) {
25                 min = cuts[j];
26             }
27         }
28         return min + 1;
29     }
30 
31     public static boolean isPalindrome(String s) {
32         int len = s.length();
33         int i = 0, j = len - 1;
34         while (i < j) {
35             if (s.charAt(i) != s.charAt(j)) {
36                 return false;
37             }
38             i++;
39             j--;
40         }
41         return true;
42     }
43 }