[Leetcode] 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的方法的话时间复杂度为O(n^2)，情况如下：

1. i == j, dp[i][j] = true, 单个字符自己肯定是回文字符串
2. i+1 == j, dp[i][j] = true, 两个字符的时候相等的话就是回文字符串
3. 其他情况，当i和j的字符相同而且dp[i+1][j-1]为回文的话，那么dp[i][j]也是回文

在寻找最小的cut的时候，也是O(N^2)级别的DP，dp[j] = argmin dp[t] + 1且 t+1到j为回文，注意处理一下t为0的特殊情况就可以了。

    public int minCut(String s) {
        if(s == null) return 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i == j)
                    dp[i][j] = true;
                else if(i+1 == j) {
                    if(s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                    else 
                        dp[i][j] = false;
                }
                else {
                    if(dp[i+1][j-1] == true && s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
            }
        }
        int[] cut = new int[n];
        for(int i = 0; i < n; i++) {
            cut[i] = Integer.MAX_VALUE;
            for(int j = 0; j <= i; j++) {
                if(j == 0 && dp[j][i] == true)
                    cut[i] = 0;
                else if(dp[j][i] == true)
                    cut[i] = Math.min(cut[j-1]+1, cut[i]);
            }
        }
        return cut[n-1];
    }