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