131. Palindrome Partitioning (Recursion, DP)

class Solution {
public:
    vector<vector<string>> partition(string s) {
        results.clear();
        int sLength = s.length();
        
        vector<vector<bool>> flag(sLength, vector<bool>(sLength,false)); //flag[i][j]纪录i到j是否是回文数
    
        for (int i=0;i<sLength;i++)
        {
            for(int j=0;j<=i;j++)
                if(s[i]==s[j]&&(i-j<2||flag[j+1][i-1])) //动态规划状态转移方程
                {
                    flag[j][i]=true;
                }
        }

        vector<string> pre;
        dfs(s,flag,pre,0);
        return results;
    }
    void dfs(const string &s, vector<vector<bool>> &flag, vector<string> &pre, int depth)
    {
        if(depth>=s.length()) //结束条件：最后一个字符已遍历
        {
            results.push_back(pre);
            return;
        }
        
        for(int i = depth; i<s.length(); i++)
        {
            if(flag[depth][i])
            {
                pre.push_back(s.substr(depth, i-depth+1)); //遍历前将当前找到的回文数加入
                dfs(s,flag,pre,i+1);
                pre.pop_back(); //回溯
            }
        }
    }
private:
    vector<vector<string>> results;
};