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",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
题意：给定字符串s，分割s，使其每个子串都是回文串，至少需要切几下。
思路：动态规划。维护数组dp[ ] ，dp[ i ]代表（0 ，i）最小的回文切割。遍历字符串，当子串s.substr(0,i+1)（包括 i 位置的字符）是回文时，dp[i]=0，即表示不用切割，若不是回文，则令dp[ i ]=i ,表示至少要切 i 刀（有i+1个字符）。对于任意大于1的 i，如果s.substr(j,i+1)（j<=i,即遍历i之前的每个子串）
是回文时，转移方程：dp[i]=min(dp[i],dp[j-1]+1)，因为若是，则只要增加一刀，就可以分为两个子串了；若不是，则取dp[i]=min(dp[i],dp[i-1]+1)，因为，为回文串时，状态转移方程中j-1>=0，说明，首字符没有考虑，若出现如“efe”的情况时，dp[i] 的值就小于dp[ i-1 ]+1。代码如下：
class Solution {
public:
int minCut(string s)
{
int len=s.size();
if(len<) return ;
vector<int> dp(len,);
for(int i=;i<len;i++)
{
if( !isPalin(s,,i))
dp[i]=i;
}
for(int i=;i<len;++i)
{
for(int j=;j<i;j++)
{
if(isPalin(s,j,i))
dp[i]=min(dp[i],dp[j-]+);
else
dp[i]=min(dp[i],dp[i-]+);
}
}
return dp[len-];
}
bool isPalin(string &s,int l,int r)
{
int i=l,j=r;
while(i<j)
{
if(s[i] !=s[j])
return false;
i++;
j--;
}
return true;
}
};
博友Grandyang，使用DP简化了每次第（j,i+1）之间的是否为回文串的判断。