链接

https://leetcode-cn.com/problems/palindrome-partitioning-ii/

耗时

解题：32 min
题解：25 min

题意

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

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

思路

dp[i] 表示 s[0:i] 的字符串的最少分割次数。

d p [ i ] = { 0            ( s [ 0 : i ] 是 回 文 串 ) min ⁡ j = 0 i − 1 ( d p [ j ] + 1 ) 在 s [ j + 1 : i ] 是 回 文 串 的 情 况 下    ( s [ 0 : i ] 不 是 回 文 串 ) dp[i] = \begin{cases} 0 \ \ \ \ \ \ \ \ \ \ (s[0:i]是回文串) \\ \min_{j=0}^{i-1}(dp[j]+1) 在 s[j+1:i]是回文串 的情况下 \ \ (s[0:i]不是回文串) \end{cases} dp[i]={0          (s[0:i]是回文串)minj=0i−1​(dp[j]+1)在s[j+1:i]是回文串的情况下  (s[0:i]不是回文串)​

判断回文串，is_palindrome[i][j] 表示 s[i:j] 是否是回文串。

i s _ p a l i n d r o m e [ i ] [ j ] = { t r u e , i ≥ j i s _ p a l i n d r o m e [ i + 1 ] [ j − 1 ] ∧ s [ i ] = = s [ j ] , o t h e r w i s e is\_palindrome[i][j] = \begin{cases} true, i \geq j \\ is\_palindrome[i+1][j-1] \wedge s[i] == s[j], otherwise \end{cases} is_palindrome[i][j]={true,i≥jis_palindrome[i+1][j−1]∧s[i]==s[j],otherwise​

时间复杂度： O ( n 2 ) O(n^2) O(n2)

AC代码

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

        return dp[n-1];
    }
};