//这是对前面回文串分割的优化算法，这个时间复杂度是O(n^2) // 方法是计算最小分割次数时，不用再去遍历字符串判断是否回文，而是先将字符串是否回文的结果保存下来，用一个二维数组来保存，i表示开始字符，j表示结束字符 //判断字符串是否回文就变成了求（i,j)区间是否是回文字符串，因此也可以用动态规划算法来求解，dp[i,j]表示从i到j字符串是回文的 //转移方程：判断（i,j)是否回文>>>s[i]==s[j] && (i+1.j-1）回文 //由于判断从i开始的字符串是否回文需要知道从i+1开始是否回文，所以我们需要从后往前开始递推，也就是从字符串末尾开始遍历  //初始化：当i==j也就是只有一个字符时，dp[i,j]结果是true;当i+1==j时，如果是s[i]==s[j]那么dp[i,j]是true;其他情况当s[i]==s[j] && dp[i+1.j-1]时，dp[i,j]是true；
public class OptimizePalindromeString {
    public static boolean[][] ispalind(String s){
        int len=s.length();
        //二维数组存储(i,j)区间的是否回文的真值只需要更新矩阵的一半，利用二维数组来保存i到j字符串的回文真值情况
        boolean[][] palind=new boolean[len][len];
        for(int i=len-1;i>=0;i--){//i表示行
            for(int j=i;j<len;j++ ){//j表示列
                if(j==i){
                    //i和j是同一个字符下标
                    palind[i][j]=true;
                }else if(j==i+1){
                    //i和j间隔一个字符
                   palind[i][j]=s.charAt(i)==s.charAt(j);
                }else{
                    //i和j间隔多个字符
                    palind[i][j]=s.charAt(i)==s.charAt(j) && palind[i+1][j-1];
                }
            }
        }
        return palind;
}

    public static int minCut (String s) {
        int len=s.length();
        if(len==0){
            return 0;
        }
        int[] mincut=new int[len+1];
        boolean[][] palind=ispalind(s);
        //首先初始化前i个字符的切割次数是字符个数减1
        for(int i=1;i<=len;i++){//从第一个字符串开始记录初始切割次数
            mincut[i]=i-1;
        }
        for(int i=2;i<=len;i++){//i是遍历字符串的，因为第一个字符的最小切割次数就是0，所以直接从第二个字符开始判断
            if(palind[0][i-1]){
                //第i个字符的索引是i-1,如果前i个字符是回文那么直接得出前i个字符的最小切割次数就是0；
                mincut[i]=0;
                continue;
            }
            for(int j=1;j<i;j++){//j是用来找最小切割次数的，找前i个字符的最小切割次数时，如果前i个不回文，那么就要从第一个字符开始去找最小切割次数知道i下标
                if(palind[j][i-1]){
                    //如果从j+1到i个字符回文，那么就mincut[i]就是利用算出的前j个字符的最小切割次数再+1即可
                    mincut[i]=Math.min(mincut[i],mincut[j]+1);
                }
            }
        }
        return mincut[len];
    }
}