131.分割回文串——medium-回溯 dp

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning

思路：
使用dp保存每个子串是否为回文串，然后使用回溯
dp转移过程须注意

• i 与 i + 1关联，i循环要倒序（先推大，大作为已知，再推小）
• j 与 j - 1关联，j循环要顺序（先推小，小作为已知，再推大）

  var partition = function (s) {
    let ans = [];
    const dfs = (start, path) => {
        if (start === s.length) {
            ans.push([...path]);
            return;
        }
        for (let i = start; i < s.length; i++) {
            if (!dp[start][i]) {
                continue;
            }
            path.push(s.slice(start, i + 1));
            dfs(i + 1, path);
            path.pop();
        }
    };
    let n = s.length;
    let dp = new Array(n).fill(undefined).map(() => {
        return new Array(n).fill(false);
    });
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    dfs(0, []);
    return ans;
  };