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.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

題解：
類似矩陣連乘的動歸思路。
dp[i][j]=min(dp[i][k]+dp[k+1][j]+1), i<=k<j.
但是用這個方程的時間是O(n^3)，簡化dp[i][j]為dp[i]，表示從0到i的minCut.
dp[i]=min(dp[k]+1(s[k+1, i]是回文串, dp[k]+i-k(s[k+1, i]不是回文串)), 0<=k<i.
這個方法在BOJ上過了，但是在leetcode上面 Judge Large 還是超時。。。
還沒找到更快的方法。。。路過的人幫解一下吧。。。
class Solution {
public:
    bool IsPalindrome(string s, int i, int j){
        if(i==j)
            return true;
        while(i<j){
            if(s[i++]!=s[j--])
                return false;
        }
        return true;
    }
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s.length();
        if(n==0 || n==1)    
            return 0;
        vector<int> min;
        for(int i=0; i<n; i++)
            min.push_back(0);
        int tmp, ans;
        for(int inter=1; inter<n; inter++){
            if(IsPalindrome(s, 0, inter)){
                min[inter]=0;
            }
            else{
                ans = n+1;
                for(int k=0; k<inter; k++){
                    if(IsPalindrome(s, k+1, inter))
                        tmp = min[k]+1;
                    else
                        tmp = min[k]+inter-k;
                    if(tmp<ans)
                        ans = tmp;
                }
                min[inter]=ans;
            }
        }
        return min[n-1];   
    }
};

經高人hadn't指點，超時是因為判斷回文串太慢，加上記憶化數組判斷回文串就pass了^-^
class Solution {
public:
    vector< vector<int> > map;
    int IsPalindrome(string &s, int i, int j){
        if(i>j) return false;
        if(map[i][j]!=-1)
            return map[i][j];
        if(i==j){
            return map[i][j] = 1;
        }
            
        if(s[i]!=s[j])
            return map[i][j] = 0;
        else{
            if(j-i==1)
                return map[i][j] = 1;
            else
                return map[i][j] = IsPalindrome(s, i+1, j-1);
        }
            
        
    }
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s.length();
        if(n==0 || n==1)    
            return 0;
        vector<int> min, vtmp;
        
        min.clear(); vtmp.clear(); map.clear();
        for(int i=0; i<n; i++){
            min.push_back(0);
            vtmp.push_back(-1);
        }
        for(int i=0; i<n; i++)
            map.push_back(vtmp);
            
        int tmp, ans;
        for(int inter=1; inter<n; inter++){
            if(IsPalindrome(s, 0, inter)){
                min[inter]=0;
            }
            else{
                ans = n+1;
                for(int k=0; k<inter; k++){
                    if(IsPalindrome(s, k+1, inter))
                        tmp = min[k]+1;
                    else
                        tmp = min[k]+inter-k;
                    if(tmp<ans)
                        ans = tmp;
                }
                min[inter]=ans;
            }
        }
        return min[n-1];   
    }
};