题目内容

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

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

示例

示例 1：

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

示例 2：

输入：s = “a”
输出：0

示例 3：

输入：s = “ab”
输出：1

提示

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

题解

本题考查动态规划。

首先，确定状态表示。设F[i]表示S[1-i]的所有分割方案的中步骤的最小值。

然后，确定状态计算。根据最后一个部分的划分范围，将集合分为1到i，2到i，3到i，…，i到i，i个部分。因此递推关系式可以为：当最后一段确定为k到i时，那么F[i] = F[k-1] + 1，在答案中去全局最小值即可。

另外，为了快速判断某一段是否是回文串，我们还是要沿用前一道题的预处理的方法，用布尔数组把字符串的回文串情况预处理出来。

具体，请看代码。

代码

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' '+ s;
        vector<vector<bool>> g(n+1,vector<bool>(n+1));
        vector<int> f(n+1,1e8);

        for(int j = 1; j<=n; j++){
            for(int i = 1; i <= n; i++){
                if(i == j)g[i][j] = true;
                else if(s[i] == s[j]){
                    if(i+1 > j-1||g[i+1][j-1]) g[i][j] = true;
                }
            }
        }
        f[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i ;j++){
                if(g[j][i]){
                    f[i] = min(f[i],f[j-1]+1);
                }
            }
        }
        return f[n] - 1;
    }
};