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.

 1 class Solution { 2 public: 3     int minCut(string s) { 4         5         int n=s.length(); 6         vector<vector<bool> > isP(n,vector<bool>(n,false)); 7         8         for(int i=n-1;i>=0;i--) 9         {10             for(int j=i;j<n;j++)11             {12                 if(s[i]==s[j]&&(j-i<=1||isP[i+1][j-1])) isP[i][j]=true;13             }14         }15        16         vector<int> dp(n+1);17         dp[n]=-1; //注意边界条件，表示了dp[i]无需分割时,dp[i]=dp[n]+1=0;18         for(int i=n-1;i>=0;i--)19         {20             int minCut=INT_MAX;21             for(int k=i+1;k<n+1;k++)22             {23                 if(isP[i][k-1]&&minCut>dp[k]+1)24                 {25                     dp[i]=dp[k]+1;26                     minCut=dp[i];27                 }28             }29         }30        31         return dp[0];32     }33 };