本文共 915 字，大约阅读时间需要 3 分钟。

问题描述

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

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

示例 1：

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

示例 2：

输入：s = "a"输出：0

示例 3：

输入：s = "ab"输出：1

提示：

1 <= s.length <= 2000s 仅由小写英文字母组成

解题思路

设 f[i]表示字符串的前缀 s[0…i]的最少分割次数。要想得出 f[i] 的值，我们可以考虑枚举 s[0…i]分割出的最后一个回文串，这样我们就可以写出状态转移方程：

注意到上面的状态转移方程中，我们还少考虑了一种情况，即 s[0…i]本身就是一个回文串。此时其不需要进行任何分割，即：

f[i]=0

那么我们如何知道 s[j+1…i]或者 s[0…i]是否为回文串呢？我们可以使用与中相同的预处理方法，将字符串 ss 的每个子串是否为回文串预先计算出来，即：

代码实现

class Solution {       public boolean f[][];     //判断以i为起点，j为终点的字符串是否是回文串    public int n;             //字符串s的长度    public int dp[];          //dp[i]表示以i为最后一个元素的子字符串的最少分割次数    public int minCut(String s) {           n=s.length();        //按最长回文子串的思路填充f[][]        f=new boolean[n][n];        if(n==0 || n==1){               return 0;        }        char []cs=s.toCharArray();        for(int i=0;i