LeetCode 132. 分割回文串 II

题目描述

难度：Hard

相关话题：动态规划

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

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

示例:

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

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @param {string} s
 * @return {number}
 */
var minCut = function(s) {
  let N=s.length
  let dp=Array(N+1).fill(0)
  let palin=Array(N).fill().map(n=>Array(N).fill(false))
  for(let i=0;i<N;i++) palin[i][i]=true

  dp[0]=-1
  for(let i=2;i<dp.length;i++){
    dp[i]=dp[i-1]+1
    for(let j=1;j<i;j++){
      if(s[i-1]===s[j-1]){
        if(i-j<=1 || palin[j][i-2]){
          dp[i]=Math.min(dp[i],dp[j-1]+1)
          palin[j-1][i-1]=true
        }
      }
    }
  }
  return dp[N]
};