這題要把字串 s 分成每個子字串都是回文的狀態，且要算需的最小分割次數，就是對一個字串，要在最少的地方切，讓每一個切割後的部分都是回文。

思路：
狀態定義，dp[i] 表從字串的開頭到第 i 個位置需要的最小切割次數，isPalindrome[i][j] 是一個布林矩陣，用來記從位置 i 到位置 j 的子字串是不是回文，初始狀態，dp[0] = 0表從字串的開頭到第 0 個位置不用切割，因為一個字母本身就是回文。遞推關係，對每個位置 i，要找出所有可能的切割點 j（0 ≤ j < i），如果 isPalindrome[j+1][i] 是 True，就表示從 j+1 到 i 是一個回文，這樣就更新 dp[i] 的最小值變 dp[j] + 1，表在位置 j 之後再一次切割，判斷回文用 isPalindrome[i][j] 的布林矩陣，可以快速判斷子字串是不是回文，也就是，s[i:j+1] 是回文如果且僅如果 s[i] == s[j] 且 isPalindrome[i+1][j-1] 是回文。

程式碼：
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
#dp[i] 表 s[0:i+1] 的最小切割數
dp = [i for i in range(n)]
#is_palindrome[i][j] 表 s[i:j+1] 是不是回文
is_palindrome = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(i + 1):
            if s[j] == s[i] and (i - j <= 1 or is_palindrome[j + 1][i - 1]):
                is_palindrome[j][i] = True
                if j == 0:
                    dp[i] = 0  # 如果 s[0:i+1] 是回文，不用切割
                else:
                    dp[i] = min(dp[i], dp[j - 1] + 1)  # 找到最小的切割數
    return dp[-1]

解釋：
動態規劃表 dp，dp[i] 用來記從字串開頭到第 i 個位置所需的最小切割次數，初始情況，最差情況是 i 之前的每個字元都要分割（ dp[i] = i），回文判斷表 is_palindrome，is_palindrome[i][j] 是個布林矩陣，用來記從位置 i 到 j 的子字串是不是回文，如果 s[i] == s[j] 且內部子字串也為回文，就可以確定 s[i:j+1] 是回文。
遞推公式：
如果 s[0:i+1] 是回文，就不用切割，dp[i] = 0，如果子字串是回文，就算 dp[j-1] + 1，表在 j 處切割一次，找出所有可能的最小值。

時間複雜度O(n^2)，因為要遍歷所有的子字串做回文判斷和最小切割計算。
空間複雜度O(n^2)，因為要一個二維矩陣來存回文判斷結果。

心得：
這道題讓我理解動態規劃結合其他算法技巧（像回文檢測）在解決復雜問題上的能力，因為提目要求的分割讓人覺得有點繁瑣，但透過特別的狀態設計，可以有效解決問題，且降低時間複雜度，這題讓我更熟悉麼根據問題要求設計動態規劃表跟狀態轉移方程的過程，也讓我體會到處理回文問題時需要靈活用子串的特性。