給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文。
返回符合要求的 最少分割次數(shù) 。
輸入：s = "aab"
輸出：1
解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串。

解題用到兩次DP。

快速判斷回文串

使用一個二維數(shù)組is_palindrome[][]來快速判斷回文串。而該二維數(shù)組，可以根據(jù)公式is_palindrome[i][j]=is_palindrome[i+1][j-1] && s[i]==s[j]得出。

計算最小切割數(shù)

假設(shè)對于長度為n的字符串s，當(dāng)s[i+1,..,n]為回文串時，一種符合要求的可能的切割數(shù)等于s[1,..,i]的最小切割數(shù)加1。如要計算最小切割，只需要對于所有可能的回文串s[i+1,...,n]，計算可能的最小切割數(shù)，最后返回最小值。

復(fù)雜度

時間和空間的復(fù)雜度均為O(n^2)。

class Solution:
    def minCut(self, s: str) -> int:
        str_len = len(s)
        is_palindrome = [[False] * str_len for _ in range(str_len)]

        # initialise the 2D array
        for idx in range(str_len):
            is_palindrome[idx][idx] = True
            if idx + 1 < str_len:
                is_palindrome[idx][idx + 1] = s[idx] == s[idx + 1]

        # Update the array in such an order
        # 0-2, 1-3, 2-4, ..., n-3-n-1
        # 0-3, 1-4, 2-5, ..., n-4-n-1
        # ...
        # ...
        # 0-n-1
        for length in range(3, str_len + 1):
            for idx in range(0, str_len - length + 1):
                start = idx
                end = idx + length - 1
                is_palindrome[start][end] = is_palindrome[start + 1][end - 1] and s[start] == s[end]

        minCuts = list(range(str_len))
        for idx in range(str_len):
            if is_palindrome[0][idx]:
                # if string s[0,..,idx] is palindrome, there
                # is no need to cut
                minCuts[idx] = 0
            else:
                # for the string s, one possible minimal cut is
                # the minimal cut s[0,..,i] + 1 given the condition
                # that s[i + 1,..,n - 1] is palindrome. To get the min
                # cut, just need to iterate i from 0 to n - 2, and
                # keep the minimal cut along the way 
                min_cut = minCuts[idx]
                for last_sub_string_start_idx in range(1, idx + 1):
                    if is_palindrome[last_sub_string_start_idx][idx]:
                        min_cut = min(
                            min_cut,
                            minCuts[last_sub_string_start_idx - 1] + 1
                        )
                minCuts[idx] = min_cut

        return minCuts[str_len - 1]