public int minCut(String s) {
        int len = s.length();
        int[] min = new int[len];
        boolean[][] p = new boolean[len][len];

        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                p[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 2 || p[i + 1][j - 1]);
            }
        }

        for(int i = 0; i < len; i++){
            if(p[0][i]){
                min[i] = 0;
            }else{
                int rs = len;
                for(int j = 0; j < i; j++){
                    if(p[j + 1][i]){
                        rs = Math.min(rs, min[j] + 1);
                    }
                }
                min[i] = rs;
            }
        }
        return min[len - 1];
    }