LC

分割回文串(求方案)
分割回文串(求最小分割数)

利用DP预处理一个字符串的前缀数组

关于回文串的题目，有一个比较常用的优化，就是预先处理出一个前缀数组f。f[i,j]表示s[i~j]是否为回文串。

求解的思路是利用递推，如果s[i~j]是回文串，必然有s[i] == s[j]并且f[i+1,j-1]为真。于是得到了DP的递推式。

Tips①：这个递推比较特别，在二维数组中是从左下角更新上来的。因此在做DP时，不能按照先i后j的方式来遍历，因为我们需要保证在计算f[i,j]时, f[i+1,j-1]已经被算出来了。所以迭代的顺序应该是先j 后i

Tips②： 边界情况，当i ==j 或者 i + 1 > j - 1（说明只有2个字符）时，f[i,j]为真。

时间复杂度$O(n^2)$.

求方案

直接DFS即可。

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> f;

    vector<vector<string>> partition(string s) {
        int n = s.size();
        f = vector<vector<bool>>(n, vector<bool>(n));

        for(int j = 0; j < n; j++) {  // 先j后i，因为f[i][j]是从左下角递推上来的
            for(int i = 0; i <= j; i++) {
                if(i == j) f[i][j] = true;
                else if(s[i] == s[j]) {
                    if(i + 1 > j - 1 || f[i + 1][j - 1])
                        f[i][j] = true;
                }
            }
        }

        dfs(0, s);
        return res;
    }

    void dfs(int u, string& s) {
        if(u == s.size()) res.push_back(path);
        else {
            for(int i = u; i < s.size(); i++) {
                if(f[u][i]) {
                    path.push_back(s.substr(u, i - u + 1));
                    dfs(i + 1, s);
                    path.pop_back();
                }
            }
        }
    }
};

求最小分割数

这是一个DP问题。DP其实是一种high level的枚举，相较于暴搜，DP每次枚举的是一类方案，而暴搜每次只枚举一个方案。因此DP会更快。

集合定义：设$f[i]$表示$s[1\sim i]$的最少分割成多少串回文串

集合计算：$f[i]$由$f[k]$，$k \in [1, i]$更新而来。如果$s[k \sim i]$是回文串，那么$f[i] = f[k - 1] + 1$，然后所有的$f[k]$取一个min即可。

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 <= j; 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 k = 1; k <= i; k++) {
                if(g[k][i]) {
                    f[i] = min(f[i], f[k - 1] + 1);
                }
            }
        }
        return f[n] - 1; // f[n]表示最少有多少块，题目问的是最少切多少刀，所以减一
    }
};