132 Palindrome Partitioning II

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.

class Solution {
public:
    int minCut(string s) {
        if (s.size()<=1)
            return 0;
        vector<int> res = vector<int>(s.size(),0);
        bool palindrome[s.size()][s.size()];
        for (int i=0;i<s.size();i++)
            for (int j=0;j<s.size();j++)
                palindrome[i][j]=true;
        for (int j=0;j<s.size();j++)
        {
            for (int i=0;i<j;i++)
            {
                if (!(s[j]==s[i] && (i+1>=j-1 || palindrome[i+1][j-1])))
                    palindrome[i][j]=false;
            }
        }
        for (int i=0;i<s.size();i++)
        {
            int cut=INT_MAX;
            for (int j=0;j<=i;j++)
            {
                if (palindrome[j][i])
                {
                    cut = min(cut,(j>=1?res[j-1]:0)+1);
                }
            }
            res[i]=cut;
        }
        return res[s.size()-1]-1;
    }
    
};