2021-06-08：一個字串至少要切幾刀能讓切出來的子串都是迴文串？
福大大 答案2021-06-08：
方法一、自然智慧，從左往右，嘗試切。迴文判斷是O（N**2）。
時間複雜度是O（N**3），空間複雜度是O（N）。
方法二、對字串範圍做是否是迴文串的dp。dp［i］［j］=true是［i，j］範圍上是迴文串，dp［i］［j］依賴左下方。消耗O（N**2）的空間。
再弄個dp2，相當於方法一的遞迴。dp2［i］相當於從i的位置切下去。消耗O（N）的空間。
時間複雜度是O（N**2）。空間複雜度是O（N**2）。
程式碼用golang編寫。程式碼如下：
package mainimport （ “fmt” “math” “math/rand” “time”）func main（） { rand。Seed（time。Now（）。Unix（）） const TOTAL = 100 count ：= 0 for i ：= 0； i < TOTAL； i++ { s ：= genRandString（） ret1 ：= minCut1（s） ret2 ：= minCut2（s） if ret1 == ret2 { count++ } fmt。Println（s， ret1， ret2） } fmt。Println（“總數：”， TOTAL） fmt。Println（“正確數：”， TOTAL）}func genRandString（） string { ans ：= make（［］byte， rand。Intn（5）+50） for i ：= 0； i < len（ans）； i++ { ans［i］ = byte（‘A’ + rand。Intn（26）） } return string（ans）}func isPalindromeString（s string） bool { if len（s） <= 1 { return true } N ：= len（s） for i ：= 0； i < N/2； i++ { if s［i］ ！= s［N-i-1］ { return false } } return true}//自然智慧，遞迴。func minCut1（s string） int { if len（s） <= 1 { return 0 } return process（s， 0， 0） - 1}func process（s string， start int， cut int） int { if start == len（s） { return cut } N ：= len（s） ans ：= math。MaxInt64 for i ：= start + 1； i <= N； i++ { if isPalindromeString（s［start：i］） { ans = getMin（process（s， i， cut+1）， ans） } } return ans}func getMin（a int， b int） int { if a < b { return a } else { return b }}func createCheckMap（str string， N int） ［］［］bool { ans ：= make（［］［］bool， N） for i ：= 0； i < N； i++ { ans［i］ = make（［］bool， N） } for i ：= 0； i < N-1； i++ { ans［i］［i］ = true ans［i］［i+1］ = str［i］ == str［i+1］ } ans［N-1］［N-1］ = true for i ：= N - 3； i >= 0； i—— { for j ：= i + 2； j < N； j++ { ans［i］［j］ = str［i］ == str［j］ && ans［i+1］［j-1］ } } return ans}//動態規劃func minCut2（s string） int { if len（s） < 2 { return 0 } N ：= len（s） checkMap ：= createCheckMap（s， N） dp ：= make（［］int， N+1） dp［N］ = 0 for i ：= N - 1； i >= 0； i—— { if checkMap［i］［N-1］ { dp［i］ = 1 } else { next ：= math。MaxInt64 for j ：= i； j < N； j++ { if checkMap［i］［j］ { next = getMin（next， dp［j+1］） } } dp［i］ = 1 + next } } return dp［0］ - 1}
執行結果如下：
