分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。

  • 输入：s = “aab”

  • 输出：1
    解释：只需一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。

  • 输入：s = “a”

  • 输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var minCut = function(s) {
    var n = s.length;
    var temp = new Array(n).fill(0).map(item=>new Array(n).fill(true));
    var dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    for(var i = n-1;i>=0;i--){
        for(var j = i+1;j<n;j++){
            temp[i][j] = s[i] === s[j] && temp[i+1][j-1];
        }
    }
    for(var i = 0;i<n;i++){
        if(temp[0][i]){
            dp[i] = 0;  //如果s从头到i是回文，即temp[0][i]为true
        }else{
            for(var j = 0;j<i;j++){
                if(temp[j+1][i]){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
    }
    return dp[n-1];
};