线性DP+区间DP

求最少分割次数即最少分割成几部分，分成三部分需要分割两次，分割成八部分需要分割七次，所以最后是分成的最小部分 - 1。

为了快速判断闭区间是否构成回文串，所以我们用131题一样的dp来表示i到j是否是回文串。

$ 时间复杂度O(N^2)，空间复杂度O(N^2)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> f(n + 1, vector<bool> (n + 1, false));//f[i][j]表示s[i - j]是否构成回文串
        for (int len = 1 ; len <= n ; len ++){
            for (int i = 1 ; i + len - 1 <= n; i ++){
                int j = i + len - 1;
                if (len == 1) f[i][j] = true;
                else if (s[i] == s[j]){
                    if (len == 2) f[i][j] = true;
                    else if (f[i + 1][j - 1]) f[i][j] = true;
                }
            }
        }
        vector<int> g(n + 1, 0x3f3f3f3f);
        g[0] = 0;
        for (int i = 1 ; i <= n ; i ++){
            for (int j = 1 ; j <= i ; j ++){
                if (f[j][i])
                    g[i] = min(g[i], g[j - 1] + 1);
            }
        }
        return g[n] - 1;
    }
};