ac

给定一个字符串，返回把str全部切割成回文串的最少切割数。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        String str = reader.readLine();
        int n = str.length();
        char[] arr = str.toCharArray();

        int[] dp = new int[n];
        boolean[][] p = new boolean[n][n]; // str[i...j] 是否是回文
        for(int i=0;i<n;i++){
            p[i][i] = true;
        }
        // 间距从1到n-1
        for(int i=1;i<n;i++){
            for(int j=0;j<n;j++){
                int k1 = j;
                int k2 = j + i;
                if(k1 >= n || k2 >= n){
                    continue;
                }
                if(i == 1){
                    if(arr[k1] == arr[k2]){
                        p[k1][k2] = true;
                    }
                }else {
                    if(arr[k1] == arr[k2] && p[k1+1][k2-1]){
                        p[k1][k2] = true;
                    }
                }
            }
        }
        dp[n-1] = 0;
        for(int i=n-2;i>=0;i--){
            if(p[i][n-1]){
                dp[i] = 0;
                continue;
            }
            dp[i] = Integer.MAX_VALUE;
            for(int j=i;j<n-1;j++){
                //[i,j] 是回文了
                // [j+1 ... n -1] 要dp[j+1]
                // [i...n-1] 就是 dp[j+1] 再加一次
                if (p[i][j]) {
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        int ans = dp[0];
        System.out.println(ans);
    }

}
/*
ABA
0

ABCBAEEE
1
*/