題目

給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文。返回符合要求的最少分割次數(shù) 。

例：
輸入：s = "aab"
輸出：1
解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串。

方法：動態(tài)規(guī)劃

• isPalindromic[i][j] 記錄下標(biāo)為 [i, j] 組成的字符串是否為回文串，True 表示為回文串，F(xiàn)alse 表示不為回文串
• 外部循環(huán)為從下到上的循環(huán)，內(nèi)部循環(huán)為從左到右的循環(huán)
  • 若首尾字符不同，那么一定不為回文串
  • 若首尾字符相同，那么需要繼續(xù)判斷：若 i=j，即此時只有一個字符（e.g. a），那么一定為回文串；若 j-i=1，即只有兩個字符且相等（e.g. aa），那么一定為回文串；若 j-i>1，即首尾字符間存在其他字符，那么此時應(yīng)判斷下標(biāo)為 [i+1, j-1] 組成的字符串是否為回文串，即 dp[i+1][j-1]
    ※ 思路同 647. 回文子串
• dp[i] 記錄下標(biāo)為 [0, i] 組成的字符串使其子串均為回文串的最少分割次數(shù)。因為記錄的是最少分割次數(shù)，所以初始化應(yīng)為最大值正無窮，并且初始化 dp[0] 為零
• 外部循環(huán)為對字符串 s 的循環(huán)
  • 判斷此時的字符串 [0, i] 是否回文，若回文則不需分割，將 dp[i] 設(shè)為零
  • 若不回文則需進(jìn)行分割，循環(huán)，j 表示分割點(diǎn)的下標(biāo)，那么此時字符串分為 [0, j] 和 [j+1, i] 兩部分，若第二部分回文，那么 dp[i] 的一個選擇是 dp[j]+1。因為求最少分割次數(shù)，所以取最小值

class Solution(object):
    def minCut(self, s):
        isPalindromic = [[False] * len(s) for row in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j-i <= 1 or isPalindromic[i+1][j-1]:
                        isPalindromic[i][j] = True

        dp = [float('INF')] * len(s)
        dp[0] = 0
        for i in range(1, len(s)):
            if isPalindromic[0][i]:
                dp[i] = 0
                continue
            for j in range(i):
                if isPalindromic[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]

參考

代碼相關(guān)：https://programmercarl.com/0132.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2II.html