132. 分割回文串 II

image.png

解題思路

1. 首先預(yù)計算 dp[i][j] 用來表示 s[i:j+1]是否為回文字符串
   1. 其中 dp[i][j]= s[i]==s[j] && dp[i+1][j-1]
2. 然后再設(shè) A[i] 表示為 s[0:i+1] 需要切割的次數(shù)
   1. 則有轉(zhuǎn)移方程 A[i]= A[j]+1, 其中 j<i 并且 s[j+1:i]為回文字符串
   2. 如果s[:i+1]本身為回文字符串，則A[i]=0,不需要再遍歷j

代碼

func minCut(s string) int {
    if len(s)==1{
        return 0
    }
    n := len(s)
    dp := make([][]bool,n)
    for i:=range dp{
        dp[i]=make([]bool,n)
        dp[i][i]=true
        if i>0{
            dp[i][i-1]=true
        }
    }
    for l:=2;l<=n;l++{
        for i:=0;i+l<=n;i++{
            j := i+l-1
            dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
        }
    }

    A := make([]int,n)
    A[0]=0

    for i:=1;i<n;i++{
        if dp[0][i]{
            continue
        }
        A[i]=1e9
        for j:=0;j<i;j++{
            if dp[j+1][i]{
                A[i]=min(A[i],A[j]+1)
            }
        }
    }
    // fmt.Println(A)
    return A[len(A)-1]

}


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