题目：
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.
解题：
思路类似Palindrome Partitioning，首先构造DP数组，然后再次dp，状态转移方程：
f[j] = min(f[j], f[i - 1] + 1);
f[i + 1] = min(f[i + 1], f[i] + 1);
代码：
class Solution {
public:
int minCut(string s) {
makeDP(s);
int f[SIZE];
if(s == "") return 0;
for(int i = 0; i <= s.size(); i ++)
f[i] = INF;
f[0] = 1;
for(int i = 0; i < s.size(); i ++) {
for(int j = i + 1; j < s.size(); j ++)
if(dp[i][j]) {
if(i)
f[j] = min(f[j], f[i - 1] + 1);
else
f[j] = 1;
}
f[i + 1] = min(f[i + 1], f[i] + 1);
}
return f[s.size() - 1] - 1;
}
private:
static const int SIZE = 2000;
static const int INF = 1 << 30;
bool dp[SIZE][SIZE];
void makeDP(string s) {
memset(dp, 0, sizeof(dp));
for(int i = s.size() - 1; i >= 0; i --)
for(int j = i; j < s.size(); j ++)
if(s[i] == s[j] && (i == j || j == i + 1 || dp[i + 1][j - 1]))
dp[i][j] = 1;
}
};