回文分割的最小分割次数问题（基础版）

题目描述：
给定一个字符串 s，将 s 分割成若干个子串，使得每个子串都是回文串。要求最少的分割次数，使得所有子串都是回文串。
例如：s = "aab"，一种最少分割的方案是 ["aa","b"]，只需要分割 1 次（在 "aa" 和 "b" 之间切一刀）。如果整个字符串已经是回文串，则分割次数为 0。

解题思路

这个问题可以拆解为两个子问题：

1. 判断任意子串 s[i..j] 是否是回文串。
2. 基于回文信息，计算从开头到每个位置的最小分割次数。

我们采用“预处理回文信息 + 动态规划求最小分割”的两步策略。

第一步：预处理得到回文表

定义 isPal[i][j] 表示子串 s[i..j]（闭区间）是否是回文串。
状态转移方程：

• 如果 i == j，单个字符，是回文，isPal[i][j] = true。
• 如果 i + 1 == j，两个字符，则 isPal[i][j] = (s[i] == s[j])。
• 如果 i + 1 < j，则 isPal[i][j] = (s[i] == s[j]) && isPal[i+1][j-1]。

我们可以用区间DP，按长度从小到大计算。
时间复杂度 O(n²)，空间复杂度 O(n²)。

第二步：动态规划求最小分割次数

定义 dp[i] 表示子串 s[0..i] 的最小分割次数（0 ≤ i < n）。

状态转移：

• 如果整个 s[0..i] 是回文串，则 dp[i] = 0，不需要分割。
• 否则，我们尝试在某个位置 j (0 ≤ j < i) 后面切一刀，将 s[0..i] 分成 s[0..j] 和 s[j+1..i]。
  如果 s[j+1..i] 是回文串，那么 dp[i] 可能是 dp[j] + 1（在 j 后面切一次）。
  我们枚举所有可能的 j，取最小值。

转移方程：

dp[i] = min{ dp[j] + 1 }，其中 0 ≤ j < i 且 isPal[j+1][i] 为真。

同时考虑 isPal[0][i] 为真的情况，则 dp[i] = 0。

初始化：dp[0] = 0，因为单个字符不需要分割。

最终答案：dp[n-1]。

详细步骤演示（以 s = "aab" 为例）

n = 3

1. 预处理 isPal
长度为1：
(0,0): true
(1,1): true
(2,2): true

长度为2：
(0,1): s[0]=='a', s[1]=='a' → true
(1,2): s[1]=='a', s[2]=='b' → false

长度为3：
(0,2): s[0]=='a', s[2]=='b' 不相等 → false

得到 isPal 表：

i\j 0    1    2
0   T    T    F
1   -    T    F
2   -    -    T

2. 计算 dp
初始化 dp[0]=0。

i=1：子串 "aa"

• isPal[0][1] 为 true → dp[1] = 0。

i=2：子串 "aab"

• 先看 isPal[0][2] 为 false，不能整体为回文。
• 枚举 j：
  j=0：检查 isPal[1][2] → false，不考虑。
  j=1：检查 isPal[2][2] → true，dp[2] 可能 = dp[1] + 1 = 0 + 1 = 1。
  没有其他 j，所以 dp[2] = 1。

结果：dp[2] = 1，最少分割次数为 1。

复杂度分析

• 预处理 isPal：O(n²) 时间，O(n²) 空间。
• 计算 dp：O(n²) 时间（因为对每个 i 枚举 j）。
• 总时间 O(n²)，空间 O(n²)。可以优化空间，但这里保持清晰性不展开。

核心要点

1. 用区间DP预处理任意子串是否为回文，避免重复判断。
2. 用线性DP计算从头到每个位置的最小分割次数，转移时利用回文信息。
3. 最终答案是 dp[n-1]。

如果还需要优化，可以只用一个数组 dp 并结合中心扩展法判断回文，达到 O(n²) 时间、O(n) 空间，但上面给出的两步法是最直观的区间DP思路。