LeetCode132. 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.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

思路

解法还是dp。

定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度
 a   b   a   b   b   b   a   b   b   a   b   a
                     i                                  n
如果现在求[i,n]之间的最优解？应该是多少？简单看一看，至少有下面一个解
 a   b   a   b   b   b   a   b   b   a   b   a
                    i                  j   j+1      n
此时  D[i,n] = min(D[i, j] + D[j+1,n])  i<=j <n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,
D[i] = min(1+D[j+1] )    i<=j <n

也就是说当从i往n方向一个个切割位置去试的时候，如果左边构成了回文，那么现在只需要考虑右边的切割方法，所以是 1+D[j+1]。加1是因为我们现在切割了一次。i<=j <n，在从i往n方向一个个切割位置去的试的这个过程中，求所有的 1+D[j+1]的最小值即可。

如何判断[i,j]是否是回文?这也是一个DP问题。

定义函数
P[i][j] = true if [i,j]为回文
那么
P[i][j] = ((str[i] == str[j]) && (P[i+1][j-1]));

代码

class Solution {
    public int minCut(String s){
        int len=s.length();
        int[] dp=new int[len+1];　　

　　　　 for(int i=len;i>=0;i--){
            dp[i]=len-i;　　// 对于考虑区间[i~len],初始赋给其可能的最大分割数，也就是分解为单个字符
        }
        boolean[][] pal=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){ // 左：s[i~j]  右：D[j+1~len]
                if(s.charAt(i)==s.charAt(j)&&(j-i<2 || pal[i+1][j-1]))
                {
                    pal[i][j]=true;
                    dp[i]=Math.min(dp[i],1+dp[j+1]);
                }
            }
        }
        return dp[0]-1;　// 最终要求的是分割数等于分割块数减1
    }
}

参考

https://blog.csdn.net/doc_sgl/article/details/13418125