题目是：
Given a string s,partition s such that every substring of the partition is a palindrome
Return tthe mininum cuts needed for a palindrome partitioning of s.
For example,given s="aab"
Return 1 since the palindrome partition["aa","b"]could be produced using 1cut
我的思路：
用动态数组dp[i]来记录当i+1个字符时，需要的分隔次数。
当前i个字符是回文串时，则dp[i]=0
当前i个字符不是回文串时，则dp[i]先置为i（i+1个字符需要的最大分割次数）
这个时候的dp[i]的值就由前i个字符来决定，用j来分隔前i个字符
则dp[i]=min{dp[i],dp[j-1]+1（当前j个字符是回文串时）||dp[j-1]+1+i-j（当前j个字符不是回文串时）}
代码如下：
int minCut(string s){
vector<int>dp(s,size(),s.size()-1)//默认值为字符串的最大分割次数
for(int i=0;i<s.size();i++){
dp[i]=Is_palindrome(s.substr(0,i+1))?0:i;//判断i+1个字符是不是回文串
if(dp[i]==0)continue;//如果是则继续循环
for(int j=1;j<=i;j++){
if(Is_palindrome(s,substr(j,i+1-j))){
dp[i]=min(dp[i],dp[j-1]+1);
}
else{
dp[i]=min(dp[i],dp[j-1]+1+i-j);
}
}
}
return dp[s.size()-1];
}
//判断是否是回文串
bool Is_palindrome(string s){
int begin=0;
int end=s.size()-1;
while(begin<end){
if(s[begin]<s[end]){
begin++;
end--;
}
else break;
if(begin>=end)return true;
return false;
}
}
做这条题目遇到的坑：
在判断回文串的时候，我首先想到的是STL中算法中的reverse函数，但是做的时候还是拿不准reverse函数的参数，于是采取了上面代码的方式，要是严格说起来的话也不是很难，清晰易懂，看来写代码不能拘泥于现成的东西。