DP+回溯分割回文串的系列问题

 

class Solution {
   public int minCut(String s) {
        int n=s.length();
        //对于长度为n的字符串,用[1,n]表示
        int []dp=new int[n+1];//dp[i]表示从s[0...i]的最小分割次数
        for (int i = 1; i <=n; i++) {
            if(isHuiwen(s.substring(0,i))){
                //如果是回文串,那么这一段不需要分割
                dp[i]=0;
            }else {
                dp[i]=i-1;//先设定一个最大的分割次数(i个字符最大分割i-1次)
                for (int j = 1; j <=i ; j++) {
                    if(isHuiwen(s.substring(j-1,i))){
                        //字符串分割是左闭右开的[j,i-1)
                        dp[i]=Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return dp[n];
    }

    private boolean isHuiwen(String substring) {
        int start=0;
        int end=substring.length()-1;
        while (start<end){
            if (substring.charAt(start)!=substring.charAt(end)){
                return false;
            }
            end--;
            start++;
        }
        return true;
    }
}

优化：其实判断回文串也可以使用动态规划

• base case 长度为1的肯定是字符串
• 字符串为2，两个字符相同的也是回文串 

class Solution {
       public int minCut(String s) {
        int n=s.length();
        int dp[]=new int[n+1];
        boolean[][]g=new boolean[n+1][n+1];//g[l][r]表示s[l...r]是不是回文串 也是规定第一个字符的下标为1
        for (int r =1; r <=n; r++) {
            for (int l =r ; l>=1 ; l--) {
                if(l==r){
                    g[l][r]=true;
                    //一个字符为回文串
                }else {
                    if (s.charAt(l-1)==s.charAt(r-1)){
                        if(r-l==1||g[l+1][r-1]){
                            g[l][r]=true;
                            //如果只有两个字符，说明是回文串
                            //或者  a b  b a  a==a时，,bb也是回文串 那么abba也就是回文串
                        }
                    }
                }
            }
        }
        for (int i = 1; i <=n; i++) {
            if(g[1][i]){
                dp[i]=0;
                //如果[1,i]是回文串，那么就不需要分割
            }else {
                dp[i]=i-1;
                for (int l = 1; l <=n ; l++) {
                    if (g[l][i]){
                        dp[i]=Math.min(dp[i],dp[l-1]+1);
                    }
                }
            }
        }
        return dp[n];
    }

}