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

题目描述：给定一个字符串s，将s分割成若干个子串，使得每个子串都是回文串。要求找到最少的分割次数，使得所有子串都是回文串。

例如：

• 输入："aab"
• 输出：1
• 解释：只需一次分割，将字符串分成"aa"和"b"两个回文子串。

解题过程：

1. 问题分析：

   • 我们需要将字符串分割成多个回文子串，且分割次数最少
   • 这是一个典型的区间动态规划问题，因为我们需要考虑字符串的各个子区间
   • 关键点：判断子串是否为回文 + 寻找最优分割方案

2. 状态定义：

   • 定义dp[i]表示字符串s的前i个字符（s[0...i-1]）的最小分割次数
   • 定义isPalindrome[i][j]表示子串s[i...j]是否为回文串

3. 预处理回文信息：

   • 使用动态规划预处理所有可能的子串是否为回文
   • 状态转移方程：
     • 当j-i <= 1时：isPalindrome[i][j] = (s[i] == s[j])
     • 否则：isPalindrome[i][j] = (s[i] == s[j]) && isPalindrome[i+1][j-1]

4. 主动态规划过程：

   • 基础情况：dp[0] = -1（空字符串不需要分割）
   • 对于每个位置j（1 ≤ j ≤ n）：
     • 初始化dp[j] = j-1（最坏情况：每个字符都分割）
     • 对于每个可能的分割点i（0 ≤ i < j）：
       • 如果s[i...j-1]是回文串：
         • dp[j] = min(dp[j], dp[i] + 1)

5. 算法步骤详解：

   • 步骤1：预处理回文表

     • 创建一个n×n的二维数组，记录所有子串的回文状态
     • 从长度为1的子串开始，逐步扩展到整个字符串

   • 步骤2：计算最小分割次数

     • 遍历字符串的每个结束位置
     • 对于每个结束位置，检查所有可能的分割方案
     • 如果某个子串是回文，则更新最小分割次数

6. 时间复杂度分析：

   • 预处理回文表：O(n²)
   • 主DP过程：O(n²)
   • 总时间复杂度：O(n²)

7. 空间复杂度分析：

   • 回文表：O(n²)
   • DP数组：O(n)
   • 总空间复杂度：O(n²)

示例演示（字符串"aab"）：

• 预处理回文表：

  • "a": true, "aa": true, "aab": false
  • "a": true, "ab": false
  • "b": true

• DP计算：

  • dp[0] = -1
  • dp[1] = min(dp[0] + 1) = 0（"a"是回文）
  • dp[2] = min(dp[0] + 1, dp[1] + 1) = min(0+1, 0+1) = 1（"aa"是回文）
  • dp[3] = min(dp[0] + 1, dp[1] + 1, dp[2] + 1) = min(0+2, 0+2, 1+1) = 1

最终结果为dp[3] = 1，表示需要1次分割。