A series of problems of dp+ backtracking segmentation palindrome string

 

class Solution {
   public int minCut(String s) {
        int n=s.length();
        // For length is n String , use [1,n] Express 
        int []dp=new int[n+1];//dp[i] From s[0...i] Minimum number of divisions 
        for (int i = 1; i <=n; i++) {
            if(isHuiwen(s.substring(0,i))){
                // If it's a palindrome string , Then this paragraph does not need to be divided 
                dp[i]=0;
            }else {
                dp[i]=i-1;// First set a maximum number of divisions (i Maximum segmentation of characters i-1 Time )
                for (int j = 1; j <=i ; j++) {
                    if(isHuiwen(s.substring(j-1,i))){
                        // String segmentation is left closed and right open [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;
    }
}

Optimize ： In fact, dynamic programming can also be used to judge palindrome strings

• base case The length is 1 It must be a string
• String is 2, The same two characters are also palindromes  

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] Express s[l...r] Is it a palindrome string   It also stipulates that the subscript of the first character is 1
        for (int r =1; r <=n; r++) {
            for (int l =r ; l>=1 ; l--) {
                if(l==r){
                    g[l][r]=true;
                    // One character is palindrome string 
                }else {
                    if (s.charAt(l-1)==s.charAt(r-1)){
                        if(r-l==1||g[l+1][r-1]){
                            g[l][r]=true;
                            // If there are only two characters , The description is palindrome string 
                            // perhaps   a b  b a  a==a when ,,bb It's also a palindrome string   that abba Palindrome string 
                        }
                    }
                }
            }
        }
        for (int i = 1; i <=n; i++) {
            if(g[1][i]){
                dp[i]=0;
                // If [1,i] It's a palindrome string , Then there is no need to split 
            }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];
    }

}