题目链接：132
思路
对于Palindrome的题目，首先可以考虑使用dp将所有区间的子字符串是否是Palindrome求出来，这样可以用O(1)的时间判断任意一个子串是否是Palindrome。
本题使用两次dp来完成。第一次dp是用来求区间是否是Palindrome；第二次dp用来满足题目要求。
对于第二次dp，称之为cutDp。cutDp[i]的物理意义是，切割 [0,i] 的子串最少需要多少次（注意 i 是闭区间）。
- 如果 s[0,i]（闭区间）是Palindrome，则当前串不需要切割，cutDp[i] = 0；
- 如果 s[0,i]（闭区间）不是Palindrome，则 j 从 1 开始递增，当 s[j, i] 是Palindrome时，cutDp[j - 1] + 1 便是 cutDp[i]。
func minCut(s string) int {
// palindromDp[i][j]: whether substring s[i, j] is palindrome
palindromDp := make([][]bool, len(s))
// cutDp[i]: the minCut of substring s [0:i] inclusively
cutDp := make([]int, len(s))
// init palindromeDp
for i := range palindromDp {
palindromDp[i] = make([]bool, len(s))
palindromDp[i][i] = true
}
// init cutDp
cutDp[0] = 0
// implement palindromeDp
for i := len(s) - 2; i >= 0; i-- {
palindromDp[i][i+1] = s[i] == s[i+1]
for j := i + 2; j < len(s); j++ {
palindromDp[i][j] = (s[i] == s[j]) && palindromDp[i+1][j-1]
}
}
// implement cutDp
// induction rule:
// if palindromeDp[0][i] == true, then cutDp[i] = 0
// else then cutDp[i] = min(cutDp[i--...]) + 1 if palindromeDp[i--... + 1][end] == true
for i := 1; i < len(cutDp); i++ {
if palindromDp[0][i] {
cutDp[i] = 0
} else {
minPre := i - 1
for j := 1; j <= i; j++ {
if palindromDp[j][i] {
minPre = min(minPre, cutDp[j - 1])
}
}
cutDp[i] = minPre + 1
}
}
return cutDp[len(s)-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
时间复杂度：O(n2) + O(n) = O(n2)
空间复杂度：O(n2)
