『每日一题』132.分隔回文串II

132.分隔回文串

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。

示例：
输入：s = "aab"
输出：1

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

思路

这道题挺有意思的，和分隔回文串有点类似，但又有区别，这道题需要找到最小的分隔方案，且输入的串比较长，用分隔回文串中用到的每次检查是否是回文串时用到了双指针，在大规模输入时，这种方法并不好用，我们要用动态规划进行预处理，从而减少检查字符串是不是回文串的时间，这是第一点。第二，如何定义状态，设 f[n-1] 为长 n 的字符串分隔为回文串所需要的最小次数，那么如果前 n-1 个字符为回文串，那么，f[n-1] = f[n-2] + 1，如果不是回文串，那么我们就要进行搜索，如果 0~i 为回文串，f[n-1] = f[i+1] + 1，找到遍历所有的 i 使得 f[n-1] 最小，这样就完成整个算法。

题解

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<int>> st(n, vector<int>(n));
        for (int j = 0; j < n; ++j) {
            for (int i = j; i >= 0; --i) {
                if (i == j)
                    st[i][j] = true;
                else if (j - i + 1 == 2) {
                    st[i][j] = (s[i] == s[j]);
                }
                else
                    st[i][j] = (s[i] == s[j]) && st[i+1][j-1];
            }
        }
        vector<int> f(n);
        for (int j = 1; j < n; ++j) {
            if (st[0][j])
                f[j] = 0;
            else {
                f[j] = f[j-1] + 1;
                for (int i = 1; i < j; ++i) {
                    if (st[i][j])
                        f[j] = min(f[j], f[i-1]+1);
                }
            }
        }
        return f[n-1];
    }
};