给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

题解：动态规划预处理+回溯

       采用动态规划的方法对字符串进行预处理，找出其中所有的回文子串，然后利用回溯算法枚举所有的分割方案，将不满足每个子串都是回文串的方案排除在外。

class Solution {
    List<List<String>>ans=new ArrayList<>();
    List<String>parts=new ArrayList<>();
    boolean[][]dp;
    public List<List<String>> partition(String s) {
        int l=s.length();
        dp=new boolean[l][l];
        for(int i=0;i<l;i++){
            dp[i][i]=true;
        }
        for(int i=1;i<l;i++){
            for(int j=0;j+i<l;j++){
                if(s.charAt(j)==s.charAt(j+i)){
                    if(j+1>j+i-1|| dp[j + 1][j + i - 1]){
                        dp[j][j+i]=true;
                    }
                }
            }
        }
        DFS(0,s.length(),s);
        return ans;
    }
    public void DFS(int i,int l,String s){
        if(i>l){
            return;
        }
        if(i==l){
            ans.add(new ArrayList<>(parts));
        }
        for(int k=1;k+i<=l;k++){
            if(dp[i][i+k-1]){
                parts.add(s.substring(i,i+k));
                DFS(i+k,l,s);
                parts.remove(parts.size()-1);
            }
        }
    }
}