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