题目

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

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

示例 1：输入：s = "aab" 输出：1

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

示例 2：输入：s = "a" 输出：0

示例 3：输入：s = "ab" 输出：1

提示：1 <= s.length <= 2000

s 仅由小写英文字母组成

注意：本题与主站 132 题相同：

解题思路分析

1、动态规划；时间复杂度O(n^3)，空间复杂度O(n)

func minCut(s string) int {
   if len(s) == 0 || len(s) == 1 {
      return 0
   }
   dp := make([]int, len(s)+1)
   dp[0] = -1
   dp[1] = 1
   for i := 1; i <= len(s); i++ {
      dp[i] = i - 1 // 长度N切分n-1次
      for j := 0; j < i; j++ {
         if judge(s[j:i]) {
            dp[i] = min(dp[i], dp[j]+1)
         }
      }
   }
   return dp[len(s)]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

func judge(s string) bool {
   for i := 0; i < len(s)/2; i++ {
      if s[i] != s[len(s)-1-i] {
         return false
      }
   }
   return true
}

2、动态规划+动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func minCut(s string) int {
   if len(s) == 0 || len(s) == 1 {
      return 0
   }
   dp := make([]int, len(s)+1)
   dp[0] = -1
   dp[1] = 1
   arr := getDP(s)
   for i := 1; i <= len(s); i++ {
      dp[i] = i - 1 // 长度N切分n-1次
      for j := 0; j < i; j++ {
         if arr[j][i-1] == true {
            dp[i] = min(dp[i], dp[j]+1)
         }
      }
   }
   return dp[len(s)]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

func getDP(s string) [][]bool {
   dp := make([][]bool, len(s))
   for r := 0; r < len(s); r++ {
      dp[r] = make([]bool, len(s))
      dp[r][r] = true
      for l := 0; l < r; l++ {
         if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
            dp[l][r] = true
         } else {
            dp[l][r] = false
         }
      }
   }
   return dp
}

总结

Hard题目，题目同leetcode 132.分割回文串II