Leetcode每日一题 132.分割回文串II

132. 分割回文串 II

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

分割回文串的另一种题型，求最小切割次数，从题意分析又是DP

本来想通过昨天代码改一改的，但发现复杂度可能超标，然后确实也超标了，然后就利用递增序列的dp思维去解题。

¶

class Solution {
public:
    vector< vector<int> > f;
    vector<int> dp;
    int n;

    int minCut(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));
        dp.assign(n,INT_MAX);
        for (int i = n - 1; i >= 0; --i) 
            for (int j = i + 1; j < n; ++j)
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];

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

昨天学到的dp求回文串的模板今天就用上了，用f[i][j] 标记[i~j]区间的回文串。

先说明dp[i]的含义，保存的是在[0~i]区间的最少分割次数，所以当f[0][i]为1时，也就是[0~i]为回文串时，dp[i]理所当然的要赋值为0，因为不需要分割，当遇到不是回文串的点j时，

我们就有个循环 for(int j = 0 ;  j < i ; j++)，重点就是这，每次都从[j+1~i]中判断，当f[j+1][i]为1时，就更新dp[i]，这时可以理解最长递增子序列中，当每次遇到满足值更新条件时（回文序列断开时），就要从满足条件的那点的dp值加上一（我们就要使当前点 (j) 的最少分裂次数加上1）。