LeetCode #132：Palindrome Partitioning II(分割回文串II)

题目描述

我们设 dp[i] 为串 s[0…i] 分割成全是回文的串所要求的最小次数。要计算 dp[i]，我们可尝试枚举一下 s[0…i] 中分割出的最后一个回文串。设割点为 j，那么分割出的最后一个回文串就是 s[j+1…i]。要想确定 dp[i]，我们就需要让 j 在区间 [0, i] 上从小到大遍历，找出使得 dp[i] 最小的那个分割点，即 dp[i] 从 dp[j] 转移而来，附加一次分割次数。

当然，若串 s[0…i] 本身就是回文串，就不必分割了，dp[i]=0。

核心代码如下：

if(s[0...i]是回文串) {
    dp[i] = 0;
    继续求dp[i+1];
}

for(int j = 0; j < i; j ++) {
    if(s[j + 1...i]是回文串)
        dp[i] = min(dp[i], dp[j] + 1);
}

如何判断 s[j + 1…i] 是回文串呢？在#647中已经写过了，直接搬过来就好了。

完整代码如下：

class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        vector<vector<bool>> dp1(n, vector<bool>(n, false)); // dp1即为记录s的某个区间的子串是否为回文的dp数组

        for(int i = n - 1; i >= 0; i --) {
            for(int j = i; j < n; j ++) {
                if(s[i] != s[j]) {
                    dp1[i][j] = false;
                } else {
                    if(j - i <= 2) {
                        dp1[i][j] = true;
                    } else if(dp1[i + 1][j - 1]) {
                        dp1[i][j] = true;
                    }
                }
            }
        }

        vector<int> dp2(n, INT_MAX); // dp2为本题的核心逻辑
        dp2[0] = 0;
        for(int i = 1; i < n; i ++) {
            if(dp1[0][i]) { // 当串s[0...i]本身就是回文串时，不必分割
                dp2[i] = 0;
                continue;
            }

            for(int j = 0; j < i; j ++) {
                if(dp1[j + 1][i])
                    dp2[i] = min(dp2[i], dp2[j] + 1);
            }
        }

        return dp2[n - 1];
    }
};