131.分割回文串

https://leetcode-cn.com/problems/palindrome-partitioning/

Stri ， L~R范围上能分解出多少种

枚举所有前缀是回文的

来看一下复杂度

枚举所有前缀 —-》 O(N),
然后每个后面还要去递归，
现在总的调度已经是O(N^2)了，
然后我们还要检查是不是回文串，
我们想不要遍历就能检查，
能不能做个预处理结构出来？把查回文的代价减下来。
在L~R范围上做个预处理结构出来，让我能很快地查在这个范围内的是不是回文串

来举个具体的例子
dp[i][j]的含义： str 中i~j范围是不是回文
先把两条对角线填好，

填普遍格子的时候，每个格子只与自己左下角的格子有关

这张表生成好后，

我们可以看到，我们的每个子过程都可以用到这张表，这就是高潮点

class Solution {
    boolean[][] dp = null;
    LinkedList<String> path = new LinkedList<>();
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
        dp = getdp(s.toCharArray());
        dfs(s, 0);
        return ans;
    }
    public  boolean[][] getdp(char[] str) {
        int N = str.length;
        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N - 1; i++) {
            dp[i][i] = true;
            dp[i][i + 1] = str[i] == str[i + 1];
        }
        dp[N - 1][N - 1] = true;
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                dp[i][j] = str[i] == str[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }
    public  void dfs(String s, int index) {
        if (index == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int end = index; end < s.length(); end++) {
            if (dp[index][end]) {
                path.addLast(s.substring(index, end + 1));
                dfs(s, end + 1);
                // 恢复现场
                path.pollLast();
            }
        }
    }
}