joshua分享：DP动态规划解法,时间复杂度为 O(1/4*N^3);

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;
    }
};