2021-06-10：一个字符串用最少刀数切出来的子串都是回文串，返回所有划分结果 。

2021-06-10：一个字符串用最少刀数切出来的子串都是回文串，返回所有划分结果 。

福大大 答案2021-06-10：

此题是前天的每日一题的变种。时间紧，有不对的地方，请指正。
对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。
再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。
根据dp和dp2，采用递归，就能求出答案。跟前天的每日一题不同的地方，就是这里。
时间复杂度是O(N2)。空间复杂度是O(N**2)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    s := "moonfdd"
    ret := minCutAllWays(s)
    fmt.Println(ret)
}

func minCutAllWays(s string) [][]string {
    ans := make([][]string, 0)
    ansp := &ans
    if len(s) < 2 {
        cur := make([]string, 0)
        cur = append(cur, s)
        ans = append(ans, cur)
    } else {
        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
            }
        }
        path := make([]string, 0)
        pathp := &path
        process(s, 0, 1, checkMap, dp, pathp, ansp)
    }
    return ans
}

// s[0....i-1]  存到path里去了
// s[i..j-1]考察的分出来的第一份
func process(s string, i int, j int, checkMap [][]bool, dp []int,
    path *[]string,
    ans *[][]string) {
    if j == len(s) { // s[i...N-1]
        if checkMap[i][j-1] && dp[i] == dp[j]+1 {
            *path = append(*path, s[i:j])
            *ans = append(*ans, copyStringList(*path))
            *path = (*path)[0 : len(*path)-1]
        }
    } else { // s[i...j-1]
        if checkMap[i][j-1] && dp[i] == dp[j]+1 {
            *path = append(*path, s[i:j])
            process(s, j, j+1, checkMap, dp, path, ans)
            *path = (*path)[0 : len(*path)-1]
        }
        process(s, i, j+1, checkMap, dp, path, ans)
    }
}

func copyStringList(list []string) []string {
    ans := make([]string, 0)
    for _, str := range list {
        ans = append(ans, str)
    }
    return ans
}

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 getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

执行结果如下：