LCR 094. 分割回文串 II - 力扣（LeetCode）

题目要求：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解法-1 动态规划 O(N)：

        这个题需要使用两个dp表，dp[i][j]存储以s[i]为结尾、s[j]为开头的字符串是不是回文；f[i]存储以s[0]开始、s[i]结尾的字符串全部分割成回文的最少分割次数。

        先填写dp，方法和每日一练：回文子串-CSDN博客中一样。

        然后填写f，f[i]有两种情况：

        （1）[0,i]是回文，f[i] = 0；

        （2）[0,i]不是回文，遍历j = [1,i]，如果dp[i][j]==true，则f[i]=min(f[i],f[i-1]+1)。

class Solution {
public:
    int minCut(string s) {
        int n = s.size();

        vector<vector<bool>> dp(n);
        for (int i = 0; i < n; i++)
            dp[i].resize(i + 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[i] == s[j]) {
                    if (i == j || j == i - 1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i - 1][j + 1];
                }
            }
        }

        vector<int> f(n, n - 1);
        f[0] = 0;

        for (int i = 1; i < n; i++) {
            if (dp[i][0])
                f[i] = 0;
            else
                for (int j = 1; j <= i; j++) {
                    if (dp[i][j])
                        f[i] = min(f[i], f[j - 1] + 1);
                }
        }

        return f[n - 1];
    }
};