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) {

         int n=s.length();

         vector<vector<bool> > isP(n,vector<bool>(n,false));

         for(int i=n-;i>=;i--)

         {

             for(int j=i;j<n;j++)

             {

                 if(s[i]==s[j]&&(j-i<=||isP[i+][j-])) isP[i][j]=true;

             }

         }

         vector<int> dp(n+);

         dp[n]=-; //注意边界条件，表示了dp[i]无需分割时,dp[i]=dp[n]+1=0;

         for(int i=n-;i>=;i--)

         {

             int minCut=INT_MAX;

             for(int k=i+;k<n+;k++)

             {

                 if(isP[i][k-]&&minCut>dp[k]+)

                 {

                     dp[i]=dp[k]+;

                     minCut=dp[i];

                 }

             }

         }

         return dp[];

     }

 };