132 分割回文串 2

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

返回符合要求的 最少分割次数 。

示例 1：

** 输入：**s = "aab" ** 输出：**1 ** 解释：** 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

** 输入：**s = "a" ** 输出：**0

示例 3：

** 输入：**s = "ab" ** 输出：**1

从右往左思考 1 分割出子串 b，这是回文串，那么需要解决的子问题为：把 aab 分割成一些子串，使每个子串都是回文串的最少分割次数。

2 分割出子串 bb，这是回文串，那么需要解决的子问题为：把 aa 分割成一些子串，使每个子串都是回文串的最少分割次数。

3 分割出子串 abb，这不是回文串。

4 分割出子串 aabb，这不是回文串。

判断回文串 如果 s [l]！=s [r]，那么子串肯定不是回文串。 如果 s [l]=s [r]，那么问题变成：s [l+1] 到 s [r−1] 是否为回文串？这是个和原问题相似的、规模更小的子问题，也可以用递归解决。

function minCut(S) {
    const s = S.split('');
    const n = s.length;
    const palMemo = Array.from({ length: n }, () => Array(n).fill(-1));
    const dfsMemo = Array(n).fill(-1);
    return dfs(n - 1, s, palMemo, dfsMemo);
}

function dfs(r, s, palMemo, dfsMemo) {
    if (isPalindrome(0, r, s, palMemo)) {
        return 0;
    }
    if (dfsMemo[r] !== -1) {
        return dfsMemo[r];
    }
    let res = Number.MAX_VALUE;
    for (let l = 1; l <= r; l++) {
        if (isPalindrome(l, r, s, palMemo)) {
            res = Math.min(res, dfs(l - 1, s, palMemo, dfsMemo) + 1);
        }
    }
    return dfsMemo[r] = res;
}

function isPalindrome(l, r, s, palMemo) {
    if (l >= r) {
        return true;
    }
    if (palMemo[l][r] !== -1) {
        return palMemo[l][r] === 1;
    }
    const res = s[l] === s[r] && isPalindrome(l + 1, r - 1, s, palMemo);
    palMemo[l][r] = res ? 1 : 0;
    return res;
}