回文子串分割的最小切割次数问题

题目描述：
给定一个字符串s，要求将s分割成若干个子串，使得每个子串都是回文串。求最少需要多少次切割。

解题过程：

1. 问题分析：

• 我们需要找到将字符串分割成回文子串的最小切割次数
• 例如：字符串"aab"可以分割为["aa","b"]，需要1次切割
• 如果字符串本身是回文串，则不需要切割（0次）

2. 动态规划状态定义：
   我们定义两个DP数组：

• dp[i]：表示子串s[0:i]（前i个字符）的最小切割次数
• isPal[i][j]：表示子串s[i:j+1]是否是回文串

3. 回文判断预处理：
   首先预处理所有可能的子串是否是回文串：

n = len(s)
isPal = [[False] * n for _ in range(n)]

# 单个字符都是回文串
for i in range(n):
    isPal[i][i] = True

# 两个相邻字符
for i in range(n-1):
    if s[i] == s[i+1]:
        isPal[i][i+1] = True

# 长度>=3的子串
for length in range(3, n+1):
    for i in range(n-length+1):
        j = i + length - 1
        if s[i] == s[j] and isPal[i+1][j-1]:
            isPal[i][j] = True

4. 最小切割次数计算：

dp = [0] * (n+1)

for i in range(n+1):
    dp[i] = i-1  # 最坏情况：每个字符都切割

for i in range(1, n+1):
    # 如果整个子串s[0:i]是回文串，不需要切割
    if isPal[0][i-1]:
        dp[i] = 0
        continue
    
    # 遍历所有可能的分割点
    for j in range(i):
        # 如果s[j:i]是回文串
        if isPal[j][i-1]:
            dp[i] = min(dp[i], dp[j] + 1)

5. 完整算法示例：
   以字符串"aab"为例：

• isPal预处理结果：
  • "a": True, "a": True, "b": True
  • "aa": True, "ab": False
  • "aab": False
• dp计算过程：
  • dp[1] = 0 ("a"是回文)
  • dp[2] = 0 ("aa"是回文)
  • dp[3]:
    • "aab"不是回文
    • 分割点1：s[1:3]="ab"不是回文
    • 分割点2：s[2:3]="b"是回文，dp[3] = min(dp[3], dp[2]+1) = 1
  • 最终结果：1

6. 时间复杂度优化：
   上述算法时间复杂度为O(n²)，空间复杂度为O(n²)。我们可以进一步优化空间复杂度到O(n)：

def minCut(s):
    n = len(s)
    dp = list(range(-1, n))
    
    for i in range(n):
        # 奇数长度回文
        left, right = i, i
        while left >= 0 and right < n and s[left] == s[right]:
            dp[right+1] = min(dp[right+1], dp[left] + 1)
            left -= 1
            right += 1
        
        # 偶数长度回文
        left, right = i, i+1
        while left >= 0 and right < n and s[left] == s[right]:
            dp[right+1] = min(dp[right+1], dp[left] + 1)
            left -= 1
            right += 1
    
    return dp[n]

这个优化版本利用中心扩展法判断回文，避免了预处理步骤，在实际应用中效率更高。