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.

``````

pseudo-code:

for i in 0 to s.length - 1：

if dp[i] > 0 and dp[i] < cutMin:

if s[i] to s[length - 1] is palindrome:

min = min ( cutMin, dp[i])

for j in 0 to s.length:

if s[i] to s[j - 1] is palindrome:

dp[j] = min(dp[i] + 1, dp[j])

if s[j] to s[length - 1] is palindrome:

min = min ( cutMin, dp[i])

``````

1. 当切至i的时候，如果从i到末尾已经是回文， 则应与最小cut数量进行比较，如果小于则进行cut。

2. 当到达的DP[i]已经比最小cut还大时应该返回，因为之后肯定所有后续结果都比最小cut要大，因此被剪枝(否则会TLE)

``````
class Solution {
public:
bool palindrome(const string&amp; s)
{
int i = 0, j = s.length() - 1;
while(i &lt; j)
{
if(s[i] != s[j]) return false;
else ++i, --j;
}
return true;
}

int minCut(const string&amp; s)
{
int length = s.length();
int minCut = 0x7fffffff;

if(length &gt; 1 &amp;&amp; !palindrome(s))
{
vector&lt;int&gt; dp(length, 0);
dp[0] = 0;

for(int i = 0; i &lt; length - 1; ++i)
{
if((dp[i] &gt; 0 &amp;&amp; dp[i] &lt; minCut) || i == 0)
{
if(palindrome(s.substr(i)))
minCut = min(minCut, dp[i]);
for(int j = i + 1; j &lt; length; ++j)
{
if(palindrome(s.substr(i, j - i)))
{
dp[j] = dp[j] == 0 ? dp[i] + 1 : min(dp[j], dp[i] + 1);

if(palindrome(s.substr(j)))
minCut = min(minCut, dp[j]);
}
}
}
}
}
else minCut = 0;

return minCut;
}
};
19ms
``````