给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2：
输入：s = "a"
输出：0示例 3：
输入：s = "ab"
输出：1提示：
- 1 <= s.length <= 2000
- s 仅由小写英文字母组成
解题：
// 超时了，我感觉应该是对的
func minCut(s string) int {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
r := math.MaxInt
var splits []string
var dfs func(int)
dfs = func(i int) {
if i == n {
l := len(splits)
if r > l {
r = l
}
return
}
for j := i; j < n; j++ {
if f[i][j] {
splits = append(splits, s[i:j+1])
dfs(j + 1)
splits = splits[:len(splits)-1]
}
}
}
dfs(0)
return r - 1
}官方解答：
1.动态规划
func minCut(s string) int {
n := len(s)
g := make([][]bool, n)
for i := range g {
g[i] = make([]bool, n)
for j := range g[i] {
g[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
g[i][j] = s[i] == s[j] && g[i+1][j-1]
}
}
f := make([]int, n)
for i := range f {
if g[0][i] {
continue
}
f[i] = math.MaxInt64
for j := 0; j < i; j++ {
if g[j+1][i] && f[j]+1 < f[i] {
f[i] = f[j] + 1
}
}
}
return f[n-1]
}