Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

http://www.lintcode.com/en/problem/palindrome-partitioning-ii/

Discussion

DP.
f[i]:表示[i,n-1]的min cuts
状态转移：j是从i到n-1的任意位置，如果[i,j]是palindrome，那么在i的cut数就是在j+1的cut数加1，也就是再多砍一刀就行了。 $$f[i] = min{f[j+1] + 1 | i<=j<n && [i,j]is palindrome$$.
初始化：最坏的情况。注意因为f[i]要用到f[j+1]，所以是n+1个状态。

Solution:

class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    int minCut(string s) {
        // write your code here
        int n = s.length();
        vector<int> f(n+1, 0);
        vector<vector<bool> > p(n, vector<bool> (n, false));
        for(int i= 0; i<=n; i++) {
            f[i] = n-i-1; //the worst case
        }
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if(s[i]==s[j] && (j-i<2 || p[i+1][j-1])) {
                    p[i][j] = true;
                    f[i] = min(f[i], f[j+1]+1);
                }
            }
        }
        return f[0];
    }
};

Follow up

也可以延续Palindrome Partitioning问题的思路，用DFS，这也是常规的暴力解法，动归通常是解决最多/最少/是否存在/之类的问题，扩展一下如果是求所有解问题，通常是推广到DFS方法来解决。

//O(2^n) run time
class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    int minCut(string s) {
        if(s.empty()) return 0;
        int min_cut = INT_MAX;
        dfs(s, 0, -1, min_cut);//cur_cut刚开始是-1，不是0，举个例子就知道了
        return min_cut;
    }
    void dfs(string s, int start, int cur_cut, int &min_cut) {
        if(start == s.length()) {
            if(cur_cut < min_cut) {
                min_cut = cur_cut;
            }
            return;
        }
        for(int i=start; i<s.length(); i++) {
            if(isPalindrome(s, start, i)) {
                dfs(s, i+1, cur_cut+1, min_cut);
            }
        }
    }
    bool isPalindrome(string s, int start, int end) {
        while(start <= end) {
            if(s[start] != s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};