joshua分享：DP动态规划解法,时间复杂度为 O(1/4*N^3);
palindrome-partitioning-ii
http://www.nowcoder.com/questionTerminal/1025ffc2939547e39e8a38a955de1dd3
DP动态规划解法,时间复杂度为 O(1/4 N^3);
定义：dp[i][j]表示字符串 i -> j切分成回文的答案数，
状态转移方程为：dp[i][j] = min(dp[i][t]+[t+1][j]),其中t位于区间[i, j];
求解过程：求解的方向，需要先求解出左下角的子三角形的解，才能求解dp[i][j],因此求解方向是按照矩形的正对角线开始，依次往右上方求解，最终dp[0][n-1]就是要求解的答案；
class Solution {
public:
int minCut(string s) {
int n = s.size();
if(isPalindro(s, 0, n-1)) return 0;
vector<vector<int> > dp(n, vector<int>(n, 0X7FFFFFFF));
for(int i = 0; i < n; i++) dp[i][i] = 1;
// 从矩阵的正对角线开始，依次往右上方求解
for(int col = 1; col < n; col++) {
for(int j = col, i = 0; j < n; i++, j++) {
if(isPalindro(s, i, j)) {
dp[i][j] = 1;
continue;
}
// 求解当前的[i,j]区间，一共有j-i-1种划分方法中的最优解
for(int t = i; t < j; t++) {
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t+1][j]);
}
}
}
return dp[0][n-1] - 1;
}
bool isPalindro(string &s, int i, int j) {
while(i < j) if(s[i++] != s[j--]) return false;
return true;
}
};
