LeetCode 132. 分割回文串 II（Palindrome Partitioning II） 要求：
给你一个字符串 s，请你将 s 分割成若干子串，使得每个子串都是回文串。返回最少分割次数。

例如：

• s = “aab” → 可分为 [“aa”, “b”] → 1 次分割（输出 1）
• s = “a” → 无需分割 → 输出 0

🧠 解题思路

这是一个典型的 动态规划（DP） 问题，核心在于：

1. 预处理：快速判断任意子串 s[i…j] 是否为回文。
2. 状态定义：dp[i] 表示子串 s[0…i] 的最少分割次数。
3. 状态转移：若 s[j…i] 是回文，则 dp[i] = min(dp[i], dp[j-1] + 1)。

注意：如果整个 s[0…i] 本身就是回文，则 dp[i] = 0。

✅ 步骤详解

第一步：预处理回文信息（isPal[i][j]）

使用二维布尔数组 isPal，其中 isPal[i][j] == true 表示 s[i…j] 是回文。

• 单个字符：isPal[i][i] = true
• 两个字符：isPal[i][i+1] = (s[i] == s[i+1])
• 长度 ≥3：isPal[i][j] = (s[i] == s[j] && isPal[i+1][j-1])

填表顺序：从下往上、从左往右（或按子串长度递增）。

第二步：DP 计算最少分割次数

• 初始化 dp[i] = i（最坏情况：每个字符都切一次）
• 对每个 i，遍历 j = 0 to i：
  • 如果 isPal[j][i] 为真：
    • 若 j == 0：说明 s[0…i] 整体是回文 → dp[i] = 0
    • 否则：dp[i] = min(dp[i], dp[j-1] + 1)

✅ Java 实现（清晰高效）

public class Solution {
public int minCut(String s) {
int n = s.length();
if (n = 3
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
isPal[i][j] = (s.charAt(i) == s.charAt(j)) && isPal[i + 1][j - 1];
}
}

    // Step 2: DP 计算最少分割次数
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = i; // 最坏情况：每个字符都切
        for (int j = 0; j <= i; j++) {
            if (isPal[j][i]) {
                if (j == 0) {
                    dp[i] = 0; // 整体是回文，无需分割
                } else {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
    }

    return dp[n - 1];
}

}

⚡ 优化：中心扩展法（空间 O(n)）

也可以不使用 O(n²) 的 isPal 表，而是用中心扩展实时更新 dp（见知识库中第一种解法），但逻辑稍复杂。上述方法更直观、易理解，且符合常规 DP 思维。

📊 复杂度分析

• 时间复杂度：O(n²)
  • 预处理回文：O(n²)
  • DP 填表：O(n²)
• 空间复杂度：O(n²)（isPal 表）

若用中心扩展法，可将空间降至 O(n)，但时间仍为 O(n²)。

✅ 示例验证

s = “aab”:

• isPal = true (“aa”)
• dp = 0
• dp = 0（因为 “aa” 是回文）
• dp:
  • j=0: “aab” ❌
  • j=1: “ab” ❌
  • j=2: “b” ✅ → dp = dp + 1 = 1

返回 1 ✅

如有需要，我也可以提供 记忆化搜索（DFS + Memo） 或 中心扩展优化版 的实现。