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。

用r[i]表示从0到i的的最小cut数目，则对于i+1，r[i+1] = min(r[j]+1)(0<=j<i+1 && s[j...i]是回文的)。

同时在判断是否为回文这部分，再用DP，用isPalindrome[i][j]表示从i到j的字符串是否是回文的。

代码：

1     int minCut(string s) { 2         // Start typing your C/C++ solution below 3         // DO NOT write int main() function 4         int n = s.size(); 5         vector
     
       res(n+1); 6         for(int i = 0 ; i< n + 1 ; ++i){ 7             res[i] = i - 1; 8         } 9         vector
      
       
         > p(n, vector
        
         (n, false));10         for(int i = 0; i< n; ++i){11             for(int j = 0; j <= i ; ++j){12                 if(s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])){13                     p[j][i] = true;14                     res[i + 1] = min(res[i + 1], res[j] + 1);15                 }16             }17         }18         return res[n];19     }