【DP】【String】Palindrome Partitioning II

int minCut(string s) {
    const int n = s.size();
    vector<vector<bool> > p(n, vector<bool>(n,-1)); // whether s[i,j] is palindrome
    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
            p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]); //第一步DP的核心递推式n
    vector<int> cut(n, -1);
    return minpart(s, p, cut, n-1);
    
}
int minpart(string &s, vector<vector<bool> > &p, vector<int> &cut, int n){
    int mcut = s.length();
    if(p[0][n] == true)  return 0;//一定要有Trival case, 递归算法才有起点
    for(int i = 0 ;i <= n; i++){
        if(p[i][n] == true){
            if(cut[i-1] == -1){
                cut[i-1] = minpart(s, p, cut, i-1);
            }
            int tcut = cut[i-1] + 1;
            if(tcut < mcut) mcut = tcut;
        }
    }
    return mcut;
}