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.
题目解析：
让求最后得到的分割中，最小切割次数。
方案一：
当然，利用上一题的方案，将数据切割成所有的情况保存，然后找出每一个vector<string>个数最小的那个，就能求得最终结果。
但是很可惜，如果不利用动态规划的话，直接深度优先并保存结果，会造成超时。这就必须处理重复求解的情况。
定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度
a b a b b b a b b a b a
i n
如果现在求[i,n]之间的最优解？应该是多少？简单看一看，至少有下面一个解
a b a b b b a b b a b a
i j
j+1 n
此时 D[i,n] = min(D[i, j] + D[j+1,n]) i<=j <n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,
D[i] = min(1+D[j+1] ) i<=j <n
有个转移函数之后，一个问题出现了，就是如何判断[i,j]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
P[i][j] = true if [i,j]为回文
那么
P[i][j] = str[i] == str[j] && P[i+1][j-1];
要点说明：
1、为什么要设dp[n+1]，多设一个？
当我们的程序运行的时候，如果恰好跟s[n-1]匹配了，就要用到dp[n-1+1]+1的值，如果额外处理的话，会繁琐，比较麻烦，所有多设一个dp[n]=0，也就是递归到边界的时候的情况。
2、动态规划的标记数组只是用来代表是否是回文串，最好不要将两个数组合并成一个，不然会造成不必要的麻烦，并且能不能做出来还不好说。
3、遍历的时候让i=len-1...0，j=i...len-1。
class Solution{
public:
int minCut(string s) {
int len = s.size();
int *dp = new int[len+1];
for(int i = len;i >= 0;i--)
dp[i] = len - i;
bool **matrix = new bool*[len];
for(int i = 0;i < len;i++){
matrix[i] = new bool[len];
memset(matrix[i],false,len * sizeof(bool));
}
for(int i = len-1;i >= 0;i--){
for(int j = i;j < len;j++){
if(s[i] == s[j] && (j-i<2 || matrix[i+1][j-1])){
matrix[i][j] = true;
dp[i] = min(dp[i],dp[j+1]+1);
}
}
}
return dp[0]-1;
}
};
方案二：贪心算法——实事证明，这种是不行的
看到这个题目，最小切割，可能会用到贪心算法。让以i为起点的最长回文串，先让j=len-1...i这样遍历，找到最大的j使得i...j为回文串。然后从j+1递归求解。
这种方案是行不通的：
