题目：

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.

思路：和上面一题一样，找出所有的可能，从中找出分割次数最少的。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool check(string& str,int begin,int end)
{
     int i = begin ;
     int j = end;
     for(;i<=j;i++,j--)
      if(str[i] != str[j])
        return false;
      return true;
}
void helper(string& str,int begin,int end,vector<int>& pos,int& count)
{
    int i,j,k;
    if(begin > end)
    {
        int k =0;
        for(j=0;j<pos.size();j++)
        {
           if(pos[j] != -1 && j != pos.size()-1)
           {
            k++;
            pos[j] = -1; 
           }
           /*
           cout<<str[j];
           if(pos[j] != -1)
           {
             cout<<",";
             pos[j] = -1;
           } */                       
        }   
         if(k < count)
         count = k; 
       // cout<<endl;     
    }
    for(i= begin;i<=end;i++)
    {
        if(check(str,begin,i))
        {
            pos[i] = i-begin+1;
            helper(str,i+1,end,pos,count);  
        }  
    }     
}
int PalindromePartition(string& str)
{
     if(str.length() == 0)
      return 0;
     vector<int> pos(str.length(),-1);
     int count=str.length()-1;
     helper(str,0,str.length()-1,pos,count);
     return count;
}
int main()
{
    string str("aab");
    cout<<PalindromePartition(str);
    system("pause");
    return 0;
}