题解 | #分割回文串-ii#动态规划算法

//时间复杂度O（n^3)
public class PalindromeString {
    //判断回文串
    public static boolean isPlind(String s,int start,int end){
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public static  int minCut (String s) {
        int len=s.length();
        int[] mincut=new int[len+1];
        if(len==0){
            return 0;
        }
        //设置初始值，让每个子串的最小分割次数是长度减1
        for(int i=1;i<=len;i++){
            mincut[i]=i-1;
        }
        //遍历字符串，找最小分割次数
        for(int i=2;i<=len;i++){//第一个字符的最小切割数就是0，所以从第二个字符开始
            //首先需要排除前i个字符是不是回文字符串，如果是那么前i个字符的最小切割次数就是0
            if(isPlind(s,0,i-1)){
                mincut[i]=0;
                continue;//跳过这次循环，从低三个字符开始
            }
            //如果不是，那么就需要从第一个字符开始计算
            for(int j=1;j<i;j++){
                if(isPlind(s,j,i-1)) {//如果从j+1到i-1区间是回文字符串，那么只需要计算前j个字符的最小分割次数
                    mincut[i] = Math.min(mincut[i], mincut[j] + 1);//整个字符串的最小切割次数就是原来前i个字符的切割次数跟回文串切割次数+1比较的最小值就是整个的结果
                }
            }
        }
        return mincut[len];
    }
}