public static int minCut(String s) {
		if (s == null || s.length() == 0 || s.length() == 1) {
			return 0;
		}
		boolean[][] isPalindrome = getPalindrome(s);
		int[] cut = new int[s.length() + 1];
	
		cut[0] = 0;
		for (int j = 1; j <= s.length(); j++) {
			cut[j] = Integer.MAX_VALUE;
			for (int i = 1; i <= j; i++) {
				if (isPalindrome[j - i][j - 1]
						&& cut[j - i] != Integer.MAX_VALUE) {
					cut[j] = Math.min(cut[j], cut[j - i] + 1);
				}
			}
		}
		return cut[s.length()] - 1;		
    }