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.

这个两个Dp， 一个是对那一部分是palindrome的二维dp。 还有一个是 对cut个数的一维dp。

public class Solution {
    int[][] map = null;
    public int minCut(String s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        map = new int[s.length()][s.length()];
        int[] cut = new int[s.length()];
        for(int i = 0; i < s.length(); i++)
            map[i][i] = 1;
        for(int i = 0; i < s.length() - 1; i ++){
            if(s.charAt(i) == s.charAt(i + 1)) map[i][i + 1] = 1;
            else map[i][i + 1] = -1;
        }
        for(int i = 0; i < s.length(); i ++){
            cut[i] = i;
            for(int j = i; j < s.length(); j ++){
                map[i][j] = checkPartition(s, i, j);
            }
        }
        for(int j = 0; j < s.length(); j ++){
            for(int i = 0; i < j; i ++){
                if(map[i][j] == 1) cut[j] = Math.min(cut[j], 1 + cut[i]);
            }
        }
        return cut[s.length() - 1];
    }
    public int checkPartition(String s, int start, int end){
        if(map[start][end] != 0) return map[start][end];
        if(s.charAt(start) != s.charAt(end)) return -1;
        return checkPartition(s, start + 1, end - 1);
    }
}

public class Solution {
    public int minCut(String s) {
        int leng = s.length();
        if(leng == 0 || leng == 1) return 0;
        boolean[][] isPal = new boolean[leng][leng];

        int[] dp = new int[leng]; 
        for (int i = 0; i < leng; i++) {
            dp[i] = leng - 1 - i;
        }

        for (int i = leng - 1; i >= 0; --i) {
            for (int j = i; j < leng; ++j) {
                if (s.charAt(i) == s.charAt(j) && (j <= i + 2 || (i + 1 < leng && j - 1 >= 0 && isPal[i + 1][j - 1]))) {
                    isPal[i][j] = true;
                    if(j+1 < leng){
                        dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
                    }else {
                        dp[i] = 0;
                    }
                }
            }
        }

        return dp[0];
    }
}