Leetcode 132. 分割回文串 II dp

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

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

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

示例:

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

解答 ：

这题同上一题131 分割回文串比较类似，但是在时间上要求更高

同样的 我们使用dp[i][j]表示 字符串i到j是否是回文字符串

但是即使我们有了这样的dp数组，如果使用dfs去尝试各种分割回文字符串的组合，依旧会超时tle

我们可以发现   1~n的字符串中 如何切割最小次数的回文字符串  其实是依赖于前面 1~n-1 ,1~n-2等子字符串的切割方案的 ，

而且1~n的字符串切割方案是不影响前面的切割方案的结果。 我们依旧尝试使用dp 。

 

我们就是根据K能和前面字符串组成回文的组合(查询dp) 计算出最小切割数即可

转移方程

countdp[i]  表示字符串的子字符串0~i最小切割数

if(dp[i][j] == 1 )　　//如果字符串s的子字符串i到j 是回文

countdp[j] = countdp[i]+1; //多切一次

代码如下

class Solution {
public:
    vector<vector<int>> dp;
    int ans = 9999999;
    void initDp(const string& s)
    {
　　　　　　//计算dp[i][j] 字符串s的i到j的子字符串是否是回文
        dp = vector<vector<int>>(s.size() + 10, vector<int>(s.size() + 10));
        for (int i = 0; i < s.size(); i++) { dp[i][i] = 1; }
        for (int i = 0; i < s.size() - 1; i++) {
            int l = i - 1; int r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                dp[l][r] = 1;  l--; r++;
            }
            l = i - 1; r = i + 2;
            if (s[i] == s[i + 1]) dp[i][i + 1] = 1;
            while (l >= 0 && r < s.size() && s[l] == s[r] && s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                dp[l][r] = 1; l--; r++;
            }
        }
    }
    

    int minCut(string s) {
        initDp(s);
        int count[2000];  memset(count, 0x3f, sizeof count);
        count[0] = 0;
　　　　//每次新加入的字符串和前面的字符能否组成回文，如果可以 计算下当前的最小切割数
        for (int i = 1; i < s.size(); i++) {
            count[i] = count[i - 1] + 1;
            for (int j = i-1; j >= 0; j--) {
                if (dp[j][i] == 1 && j != 0) {
                    count[i] = min(count[i], count[j-1]+1);
                }
                else if (dp[j][i] == 1 && j == 0) {
                    count[i] = 0;
                }
            }
        }

        return count[s.size()-1];
    }
};