public int minCut2(String s) {
        int length = s == null ? 0 : s.length();
        if (length == 0)
            return 0;
        int[] dp = new int[length + 1];
        for (int i = 0; i < length; ++i) {
            dp[i] = length - i;
        }
        boolean[][] palindromes = new boolean[length][length];
        for (int i = length - 1; i >= 0; --i) {
            for (int j = i; j < length; ++j) {
                if ((s.charAt(i) == s.charAt(j) && (j - i < 2)) || (s.charAt(i) == s.charAt(j) && palindromes[i + 1][j - 1])) {
                    palindromes[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0] - 1;
    }