代码1

DP
Runtime: 9 ms, faster than 82.70% of Java online submissions for Palindrome Partitioning II.

class Solution {
    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        boolean[][] isPalindrome = new boolean[n][n];
        int[] cut = new int[n];
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = 0; j <= i; j++) {
                if (c[j] == c[i] && (j + 1 > i - 1||isPalindrome[j + 1][i - 1])) {
                    isPalindrome[j][i] = true;
                    if (j == 0) {
                        min = 0;
                    } else {
                        min = Math.min(min, cut[j - 1] + 1);
                    }
                }
            }
            cut[i] = min;
        }
        return cut[n - 1];
    }
}