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.

Ideas:

DP: D[i] 从i到n的回文数个数最小值，初始值是按照每个字符作为一个回文设置的 dp[i][j] 表示从字符i到j是否为回文

public int minCut(String s) {
    int len = s.length();  

    boolean[][] P = new boolean[len][len];
    int[] D = new int[len+1];
    for (int i = 0; i <= len; i++) {
        D[i] = len-i;            
    }

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

    return D[0]-1;
}