题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-partitioning-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

动态规划,从左到右模型

尝试的是每一个作为切出来的第1部分，所有的可能性

dp[i]从出发后面所有的字符串至少分成几个部分让每个部分都是回文

不优化的化为O(n³)
需要优化检查回文的逻辑

预处理表

生成一个map,告诉你从i到j是否为回文
构建正方形表

填好第一条对角线和第二条对角线

普遍位置
map[l][r]=str[l]==str[r]&&map[l+1][r-1]

     boolean[][] isMap=new boolean[n][n];
     for(int i=0;i<n-1;i++){
    
         isMap[i][i]=true;
         isMap[i][i+1]=str[i]==str[i+1];
     }
     isMap[n-1][n-1]=true;
     for(int i=n-3;i>=0;i--){
    
         for(int j=i+2;j<n;j++){
    
             isMap[i][j]=(str[i]==str[j]&&isMap[i+1][j-1]);
         }
     }

代码

class Solution {
    
    public int minCut(String s) {
    
        char[] str=s.toCharArray();
        int n=str.length;
        if(n==0||n==1){
    
            return 0;
        }
        boolean[][] isMap=new boolean[n][n];
        for(int i=0;i<n-1;i++){
    
            isMap[i][i]=true;
            isMap[i][i+1]=str[i]==str[i+1];
        }
        isMap[n-1][n-1]=true;
        for(int i=n-3;i>=0;i--){
    
            for(int j=i+2;j<n;j++){
    
                isMap[i][j]=(str[i]==str[j]&&isMap[i+1][j-1]);
            }
        }
        int[] dp=new int[n];
        for(int i=n-1;i>=0;i--){
    
            if(isMap[i][n-1]){
    
                dp[i]=1;
            }else{
    
                int next=Integer.MAX_VALUE;
                for(int j=i;j<n;j++){
    
                    if(isMap[i][j]){
    
                        next=Math.min(dp[j+1],next);
                    }
                }
                dp[i]=next+1;
            }
        }
        return dp[0]-1;
    }
}