原文：132. 分割回文串 II(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0132/

题目：

难度：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]
};

扩展阅读：