132 分割回文串

题目链接

131. 分割回文串

132. 分割回文串 II

分析

定义 $dp[i]$ 为前缀 $s[0]$ 到 $s[i]$ 的最小分割次数

状态转移方程为 $dp[i] = \mathop{min}\limits_{l=1}^r dp[i - 1] + 1$

预先计算 $isPal[i][j]$ 表示 $s[i]$ 到 $s[j]$ 是否为回文串

遍历计算出 $dp[n - 1]$ 即可

代码实现

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        vector<vector<bool>> isPal(n, vector<bool>(n, true));

        for(int l = n - 2; l >= 0; --l)
            for(int r = l + 1; r < n; ++r)
                isPal[l][r] = s[l] == s[r] && isPal[l + 1][r - 1];

        for(int r = 0; r < n; ++r) {
            if(isPal[0][r])
                continue;
    
            int res = n;
            for(int l = 1; l <= r; ++l) {
                if(isPal[l][r])
                    res = min(res, dp[l - 1] + 1);
            }
            dp[r] = res;
        }

        return dp[n - 1];
    }
};

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$