Leetcode_132. Palindrome Partitioning II_[DP]

题目链接

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

题意同样简单明了。

解法：

由上题Palindrome Partitioning，可以得到一个解此题的思路，DFS穷举所有方案。然而，仅仅是DFS会超时。此题仅要求求得划分次数最小的方法的划分次数。在这个问题下，dfs(string &s, int idx) 返回 s[idx, s.size()-1] 这个子串最少需要多少次划分。可以发现，朴素DFS存在大量的重复计算，因为s[0, idx)子串有多少种划分法，dfs(string &s, int idx) 就会被调用多少次，而每次计算 dfs(string &s, int idx) 返回的结果都是相同的。因此，自然而然的想到记忆化搜索，也就是dp。

class Solution {
public:
    vector<vector<bool>> is_palindrome;
    vector<int> dp;
    int minCut(string s) {
        int len = s.size();
        is_palindrome = std::move(vector<vector<bool>>(len, vector<bool>(len, false)));
        dp = std::move(vector<int>(len, len+1));
        for(size_t l=1; l<=len; l++)
            for(size_t head=0; head+l-1<len; head++){
                int tail = head+l-1;
                if(l == 1)
                    is_palindrome[head][tail] = true;
                else if(s[head]==s[tail] && (head == tail-1 || is_palindrome[head+1][tail-1]))
                    is_palindrome[head][tail] = true;
            }
        int ret = len;
        dfs(s, 0);
        return dp[0]-1;
    }

    int dfs(string& s, int hp){
        if(hp == s.size())
            return 0;
        if(dp[hp] < s.size()+1)
            return dp[hp];
        int ret = s.size()+1;
        for(size_t i=s.size()-hp; i>=1; i--)
            if(is_palindrome[hp][hp+i-1])
                ret = min(ret, 1+dfs(s, hp+i));
        return dp[hp] = ret;
    }
};