public static int minCut(String s) {
    	if (null == s || 0 == s.length()) return 0;
    	int len = s.length();
    	int[] result = new int[len];
    	boolean[][] palindrome =new boolean[len][len];
    	for (int start = len - 1; start >= 0; start--) {
    		result[start] = len - start - 1;
    		for (int end = start; end < len; end++) {
				if (s.charAt(start) == s.charAt(end)) {
					if (end - start < 2) palindrome[start][end] = true;
					else palindrome[start][end] = palindrome[start+1][end-1];
				}
				if (palindrome[start][end]) {
					if (len - 1 == end) {result[start] = 0;}
					else {
						result[start] = result[start] < result[end + 1] + 1 ? 
								result[start] : result[end + 1] + 1;
					}
				}
			}
    	}
    	return result[0];
    }