132.分割回文串II——hard-dp

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

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

示例:

输入: “aab”
输出: 1
解释: 进行一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
思路：
用动态规划判断每个子串是否是回文串。
用dp[i] 表示前i个字符串至少需要割dp[i]次才能形成回文串，
如果s[0,i]是回文串：
dp[i]=0,
否则枚举分割点：
假如s[j+1,i] 是回文串,dp[i] = max(dp[i],dp[j]+1)
复杂度分析：
时间复杂度O(n) n为字符串长度
空间复杂度O(n)

var minCut = function (s) {
    let n = s.length;
    if (!n) return 0;
    let isPalindrome = 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 || isPalindrome[i + 1][j - 1])) {
                isPalindrome[i][j] = true;
            }
        }
    }
    let dp = [];
    for (let i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            dp[i] = 0;
            continue;
        }
        for (let j = 0; j < i; j++) {
            if (isPalindrome[j + 1][i]) {
                dp[i] = Math.min(dp[i] || Infinity, dp[j] + 1);
            }
        }
    }
    return dp[n - 1];
};