【力扣hot100题】（060）分割回文串

每次需要判断回文串，这点比之前几题回溯题目复杂一些。

还有我怎么又多写了循环……

class Solution {
public:
    vector<vector<string>> result;
    string s;
    bool palindromic(string s){
        for(int i=0;i<s.size()/2;i++) if(s[i]!=s[s.size()-1-i]) return 0;
        return 1;
    }
    void backtracking(int i,vector<string> &v){
        if(i==s.size()) result.push_back(v);
        for(int j=i;j<s.size();j++){
            if(palindromic(s.substr(i,j-i+1))){
                v.push_back(s.substr(i,j-i+1));
                backtracking(j+1,v);
                v.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        this->s=s;
        vector<string> v;
        backtracking(0,v);
        return result;
    }
};

看了答案发现纯递归的思路还是有些先入为主了，答案用了更好更适合的方法：动态规划，思路是先找出s中所有回文串字符串，再递归，少绕了不少弯路，很多地方都不用重复判断了，并且先用动态规划找出所有回文字符串的思路也很棒。

动态规划找回文字符串的方法是，先将判断回文串的二维数组全设为true，接着循环遍历整个数组，若两指针对应元素不同则为false。

class Solution {
public:
    vector<vector<string>> result;
    string s;
    bool dp[17][17];
    vector<string> v;
    void backtracking(int i){
        if(i==s.size()) result.push_back(v);
        else for(int j=i;j<s.size();j++){
            if(dp[i][j]){
                v.push_back(s.substr(i,j-i+1));
                backtracking(j+1);
                v.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        this->s=s;
        memset(dp,1,sizeof(dp));
        for(int i=1;i<s.size();i++){
            for(int j=0;j<i;j++){
                dp[j][i]=(s[i]==s[j])&&dp[j+1][i-1];
            }
        }
        backtracking(0);
        return result;
    }
};