回文分割的最小分割次数问题（基础版）
字数 3378 2025-12-09 01:32:20

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

题目描述

给定一个字符串 s，请你将 s 分割成一些子串，使得每个子串都是回文串。返回符合要求的最少分割次数。

例如：
输入：s = "aab"
输出：1
解释：只需进行一次分割，将 s 分割成 ["aa", "b"]。

输入：s = "a"
输出：0
解释：字符串本身就是回文，不需要分割。

输入：s = "ab"
输出：1
解释：需要进行一次分割，将 s 分割成 ["a","b"]。

题目核心：将字符串切割成若干段，使得每一段都是回文串。目标是找到完成此目标所需的最少切割次数。这是一道典型的、结合了预处理和动态规划的区间DP问题。

解题步骤详解

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

  1. 判断任意子串是否为回文串：我们需要频繁查询任意区间 [i, j] 的字符串是否是回文。如果每次都临时判断，时间复杂度会很高。因此，通常先预处理一个二维DP表 isPalindrome[i][j] 来记录这个信息。
  2. 计算最小分割次数：在知道任意子串是否为回文后，我们再通过一个一维DP数组 dp 来从前往后推导，计算到每个位置为止所需的最少分割次数。

让我们一步步来。

第一步：预处理回文信息（区间DP）

我们定义 isPalindrome[i][j] 为一个布尔值，表示字符串 s 从下标 i 到下标 j （包含两端）的子串 s[i..j] 是否是回文串。

  • 状态定义：isPalindrome[i][j] = True 当且仅当 s[i..j] 是回文。
  • 状态转移方程：如何判断一个子串是不是回文？
    • 基本情况1：如果子串长度为1（即 i == j），那么它肯定是回文。isPalindrome[i][i] = True。
    • 基本情况2：如果子串长度为2（即 j == i + 1），那么只需要判断这两个字符是否相等。isPalindrome[i][i+1] = (s[i] == s[i+1])。
    • 一般情况：对于长度大于2的子串（j > i+1），它要是回文，必须满足：
      1. 两头的字符相等：s[i] == s[j]。
      2. 去掉两头字符后的内部子串也必须是回文：isPalindrome[i+1][j-1] == True。
        因此，转移方程为：isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i+1][j-1]。
  • 计算顺序：注意，在计算 isPalindrome[i][j] 时，我们需要知道 isPalindrome[i+1][j-1] 的结果。这意味着我们需要先计算出长度更短的子串的回文状态。所以，我们应该按照子串的长度从小到大进行计算。
    • 外层循环：长度 L 从 1 到 n（n为字符串长度）。
    • 内层循环：起始下标 i 从 0 到 n-L。结束下标 j = i + L - 1。

示例 s = "aab" 的预处理过程：

  1. L=1: isPalindrome[0][0]=T, isPalindrome[1][1]=T, isPalindrome[2][2]=T。
  2. L=2:
    • i=0, j=1: s[0]('a') == s[1]('a') -> isPalindrome[0][1]=T。
    • i=1, j=2: s[1]('a') != s[2]('b') -> isPalindrome[1][2]=F。
  3. L=3:
    • i=0, j=2: 需要判断 s[0]==s[2] (a==b? 否) 并且 isPalindrome[1][1] (是T)。因为第一个条件不满足，所以 isPalindrome[0][2]=F。

得到的 isPalindrome 表：

   j:0 1 2
i
0     T T F
1       T F
2         T

第二步：计算最小分割次数（线性DP）

现在我们知道了所有子串的回文性。定义一维DP数组：

  • dp[i]：表示前缀子串 s[0..i] 要被分割成若干回文子串，所需的最少分割次数。

最终答案：dp[n-1]，即整个字符串 s[0..n-1] 的最小分割次数。

  • 状态转移：我们如何计算 dp[i]？
    • 一个最朴素的想法是，对于位置 i，我们尝试所有可能的前一个分割点 j（j 从 -1 到 i-1）。这里 j = -1 表示从开头开始切割。
    • 如果子串 s[j+1 .. i] 是回文（即 isPalindrome[j+1][i] == True），那么：
      • 在 j 处，我们已经将 s[0..j] 分割好了，其最小分割次数是 dp[j]。
      • 现在，我们把 s[j+1..i] 这整个回文块接在后面，不需要在 i 之前做新的切割。
      • 所以，通过这种分割方式，到达 i 的总切割次数是 dp[j] + 0（因为 s[j+1..i] 是完整的一块，接上去就行）。
    • 但是，如果 j = -1，意味着 s[0..i] 整个就是一个回文串，那么 dp[i] = 0，一次都不用切。
    • 综合一下，我们可以把 j=-1 的情况看作 dp[-1] = -1（一个虚拟的起始状态，切割了-1次），这样 dp[j] + 1 就正好表示在 j 后面切一刀，然后接上 s[j+1..i] 这个回文块。公式就统一了。

因此，状态转移方程为：
dp[i] = min(dp[j] + 1)，其中 j 满足 -1 <= j < i，且 isPalindrome[j+1][i] == True。

初始化：我们可以将 dp 数组初始化为一个很大的数（比如字符串长度n），因为最坏情况是每个字符都切一刀，切割次数最多为 n-1。同时，为了方便处理 j = -1 的情况，我们让 j 从0开始循环，但额外判断如果 s[0..i] 自身是回文，则 dp[i] = 0。

计算顺序：i 从 0 到 n-1 依次计算。

示例 s = "aab" 的计算过程：
n=3, 初始化 dp = [inf, inf, inf]。

  1. i=0: 子串 s[0..0] 是回文 (isPalindrome[0][0]=T)，所以 dp[0] = 0。
  2. i=1: 考虑所有以 i=1 结尾的回文子串：
    • s[0..1] ("aa") 是回文 (isPalindrome[0][1]=T)。如果整个取它，j = -1，对应 dp[1] = 0。
    • s[1..1] ("a") 是回文。这意味着在 j=0 后面切一刀 (dp[0]=0)，然后接上"s[1..1]"，总切割数 = dp[0] + 1 = 1。
    • 取最小值，dp[1] = min(0, 1) = 0。
  3. i=2: 考虑所有以 i=2 结尾的回文子串：
    • s[0..2] ("aab") 不是回文，跳过。
    • s[1..2] ("ab") 不是回文，跳过。
    • s[2..2] ("b") 是回文。这意味着在 j=1 后面切一刀 (dp[1]=0)，然后接上"s[2..2]"，总切割数 = dp[1] + 1 = 1。
    • dp[2] = 1。

最终 dp[2] = 1，与答案一致。

总结与复杂度分析

这道题巧妙地将一个“最少分割”问题，转化为“判断回文”和“最少分段”两个DP问题。

  1. 预处理阶段（区间DP）：

    • 时间复杂度：O(n²)。我们需要填充一个 n x n 的二维表。
    • 空间复杂度：O(n²)，用于存储 isPalindrome 表。可以优化为O(n)，但代码会复杂些，这里不展开。

  2. 计算分割次数阶段（线性DP）：

    • 时间复杂度：在最坏情况下，对于每个 i，我们需要检查所有 j < i，所以是 O(n²)。
    • 空间复杂度：O(n)，用于存储 dp 数组。

总时间复杂度为 O(n²)，总空间复杂度为 O(n²)。这是一个非常经典的解法，清晰地展示了如何将区间信息（回文判断）作为基础，来支持更上层的决策（最少分割）。

回文分割的最小分割次数问题（基础版） 题目描述 给定一个字符串 s，请你将 s 分割成一些子串，使得每个子串都是回文串。返回符合要求的最少分割次数。 例如： 输入：s = "aab" 输出：1 解释：只需进行一次分割，将 s 分割成 [ "aa", "b" ]。 输入：s = "a" 输出：0 解释：字符串本身就是回文，不需要分割。 输入：s = "ab" 输出：1 解释：需要进行一次分割，将 s 分割成 [ "a","b" ]。 题目核心 ：将字符串切割成若干段，使得每一段都是回文串。目标是找到完成此目标所需的最少切割次数。这是一道典型的、结合了 预处理 和 动态规划 的区间DP问题。 解题步骤详解 这个问题可以分解为两个子问题： 判断任意子串是否为回文串 ：我们需要频繁查询任意区间 [i, j] 的字符串是否是回文。如果每次都临时判断，时间复杂度会很高。因此，通常先 预处理 一个二维DP表 isPalindrome[i][j] 来记录这个信息。 计算最小分割次数 ：在知道任意子串是否为回文后，我们再通过一个一维DP数组 dp 来从前往后推导，计算到每个位置为止所需的最少分割次数。 让我们一步步来。 第一步：预处理回文信息（区间DP） 我们定义 isPalindrome[i][j] 为一个布尔值，表示字符串 s 从下标 i 到下标 j （包含两端）的子串 s[i..j] 是否是回文串。 状态定义 ： isPalindrome[i][j] = True 当且仅当 s[i..j] 是回文。 状态转移方程 ：如何判断一个子串是不是回文？ 基本情况1 ：如果子串长度为1（即 i == j ），那么它肯定是回文。 isPalindrome[i][i] = True 。 基本情况2 ：如果子串长度为2（即 j == i + 1 ），那么只需要判断这两个字符是否相等。 isPalindrome[i][i+1] = (s[i] == s[i+1]) 。 一般情况 ：对于长度大于2的子串（ j > i+1 ），它要是回文，必须满足： 两头的字符相等： s[i] == s[j] 。 去掉两头字符后的内部子串也必须是回文： isPalindrome[i+1][j-1] == True 。 因此，转移方程为： isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i+1][j-1] 。 计算顺序 ：注意，在计算 isPalindrome[i][j] 时，我们需要知道 isPalindrome[i+1][j-1] 的结果。这意味着我们需要先计算出长度更短的子串的回文状态。所以，我们应该 按照子串的长度 从小到大进行计算。 外层循环：长度 L 从 1 到 n（n为字符串长度）。 内层循环：起始下标 i 从 0 到 n-L 。结束下标 j = i + L - 1 。 示例 s = "aab" 的预处理过程 ： L=1: isPalindrome[0][0]=T , isPalindrome[1][1]=T , isPalindrome[2][2]=T 。 L=2: i=0, j=1: s[0]('a') == s[1]('a') -> isPalindrome[0][1]=T 。 i=1, j=2: s[1]('a') != s[2]('b') -> isPalindrome[1][2]=F 。 L=3: i=0, j=2: 需要判断 s[0]==s[2] ( a==b ? 否) 并且 isPalindrome[1][1] (是T)。因为第一个条件不满足，所以 isPalindrome[0][2]=F 。 得到的 isPalindrome 表： 第二步：计算最小分割次数（线性DP） 现在我们知道了所有子串的回文性。定义一维DP数组： dp[i] ：表示 前缀子串 s[0..i] 要被分割成若干回文子串，所需的最少分割次数。 最终答案 ： dp[n-1] ，即整个字符串 s[0..n-1] 的最小分割次数。 状态转移 ：我们如何计算 dp[i] ？ 一个最朴素的想法是，对于位置 i ，我们尝试所有可能的前一个分割点 j （ j 从 -1 到 i-1）。这里 j = -1 表示从开头开始切割。 如果子串 s[j+1 .. i] 是回文（即 isPalindrome[j+1][i] == True ），那么： 在 j 处，我们已经将 s[0..j] 分割好了，其最小分割次数是 dp[j] 。 现在，我们把 s[j+1..i] 这整个回文块接在后面，不需要在 i 之前做新的切割。 所以，通过这种分割方式，到达 i 的总切割次数是 dp[j] + 0 （因为 s[j+1..i] 是完整的一块，接上去就行）。 但是，如果 j = -1 ，意味着 s[0..i] 整个就是一个回文串，那么 dp[i] = 0 ，一次都不用切。 综合一下，我们可以把 j=-1 的情况看作 dp[-1] = -1 （一个虚拟的起始状态，切割了-1次），这样 dp[j] + 1 就正好表示在 j 后面切一刀，然后接上 s[j+1..i] 这个回文块。公式就统一了。 因此，状态转移方程为 ： dp[i] = min(dp[j] + 1) ，其中 j 满足 -1 <= j < i ，且 isPalindrome[j+1][i] == True 。 初始化 ：我们可以将 dp 数组初始化为一个很大的数（比如字符串长度n），因为最坏情况是每个字符都切一刀，切割次数最多为 n-1 。同时，为了方便处理 j = -1 的情况，我们让 j 从0开始循环，但额外判断如果 s[0..i] 自身是回文，则 dp[i] = 0 。 计算顺序 ： i 从 0 到 n-1 依次计算。 示例 s = "aab" 的计算过程 ： n=3, 初始化 dp = [inf, inf, inf] 。 i=0: 子串 s[0..0] 是回文 ( isPalindrome[0][0]=T )，所以 dp[0] = 0 。 i=1: 考虑所有以 i=1 结尾的回文子串： s[0..1] ("aa") 是回文 ( isPalindrome[0][1]=T )。如果整个取它， j = -1 ，对应 dp[1] = 0 。 s[1..1] ("a") 是回文。这意味着在 j=0 后面切一刀 ( dp[0]=0 )，然后接上"s[ 1..1]"，总切割数 = dp[0] + 1 = 1 。 取最小值， dp[1] = min(0, 1) = 0 。 i=2: 考虑所有以 i=2 结尾的回文子串： s[0..2] ("aab") 不是回文，跳过。 s[1..2] ("ab") 不是回文，跳过。 s[2..2] ("b") 是回文。这意味着在 j=1 后面切一刀 ( dp[1]=0 )，然后接上"s[ 2..2]"，总切割数 = dp[1] + 1 = 1 。 dp[2] = 1 。 最终 dp[2] = 1 ，与答案一致。 总结与复杂度分析 这道题巧妙地将一个“最少分割”问题，转化为“判断回文”和“最少分段”两个DP问题。 预处理阶段（区间DP） ： 时间复杂度：O(n²)。我们需要填充一个 n x n 的二维表。 空间复杂度：O(n²)，用于存储 isPalindrome 表。可以优化为O(n)，但代码会复杂些，这里不展开。 计算分割次数阶段（线性DP） ： 时间复杂度：在最坏情况下，对于每个 i ，我们需要检查所有 j < i ，所以是 O(n²)。 空间复杂度：O(n)，用于存储 dp 数组。 总时间复杂度为 O(n²)，总空间复杂度为 O(n²) 。这是一个非常经典的解法，清晰地展示了如何将区间信息（回文判断）作为基础，来支持更上层的决策（最少分割）。