Leetcode 132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

题意：一个字符串，求把它分割成回文串组合的最小分割次数。

思路：
动态规划解法。对于字符串str，用cut[i]表示从0到i的最短分割次数，用isPalind[j][k]表示从j到k是否是一个回文串。对于0..i..k，i可以是对于从0到k的任意位置，i大于0时，只要i到k是回文，就可以求出一个对于0到k的分割次数，即cut[i-1] + 1，则cut[k]是所有这些次数的最小值；如果i等于0，并且i到k就是回文，则cut[k] = 0。

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

    int len = s.length();
    int[] minCutNum = new int[len];
    boolean[][] isPalind = new boolean[len][len];

    for (int i = 0; i < len; i++) {
        int min = i;
        for (int j = 0; j <= i; j++) {
            if (s.charAt(j) == s.charAt(i) && (i - j < 2 || isPalind[j+1][i-1])) {
                if (j == 0) {
                    min = 0;
                } else {
                    min = Math.min(min, minCutNum[j-1] + 1);
                }
            }
        }
        minCutNum[i] = min;
    }

    return minCutNum[len - 1];
}