public int minCut(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}

		int[] cut = new int[s.length() + 1];
		boolean[][] isPalindrome = getIsPalindrome(s);

		cut[0] = 0;
		for (int i = 1; i <= s.length(); i++) {
			cut[i] = Integer.MAX_VALUE;
			for (int j = 1; j <= i; j++) {
				if (isPalindrome[i - j][i - 1]
						&& cut[i - j] != Integer.MAX_VALUE) {
					cut[i] = Math.min(cut[i], cut[i - j] + 1);
				}
			}
		}

		return cut[s.length()] - 1;
	}