bool isPalindrome(string& s, int l, int r) {    while(l++ < r--)         if(s[l] != s[r]) return false;    return true;}class Solution {public:    void dfs(string& s, vector<string>& vec2, size_t id) {        if(id == s.size()) {            vec.push_back(vec2);            return;        }        for(int end = id; end < s.size(); ++end) {            if(isPalindrome(s, id, end)) {                vec2.push_back(s.substr(id, end-id+1));                dfs(s, vec2, end+1);                vec2.pop_back();            }        }    }    vector<vector<string> > partition(string s) {        if(s == "") return vec;        vector<string> vec2;        dfs(s, vec2, 0);        return vec;    }private:    vector<vector<string> > vec;};

class Solution {public:    int minCut(string s) {        if(s == "" || s.size() == 1) return 0;        int n = s.size();        vector<vector<bool> > D(n, vector<bool>(n, false));        vector<int> record(n, 0);        for(int i = n-1; i >= 0; --i) {            record[i] = n-1-i;            for(int j = i; j < n; ++j) {				if(s[i] == s[j] && (j-i < 2 || D[i+1][j-1])) {					D[i][j] = true;					if(j == n-1) record[i] = 0;					else record[i] = min(record[i], record[j+1]+1);				}            }        }        return record[0];    }};