dp[i] = min( dp[j] + 1 )，对于所有满足 0 ≤ j < i 且 isPal[j+1][i] 为真的j。

最长回文子序列的长度与回文分割的最小割数 题目描述 给定一个字符串s，其长度为n。我们考虑将s分割成若干个子串，使得每个子串都是回文串。求最少的分割次数，也就是将s分割成若干个回文子串所需的最小切割数。例如，对于s = "aab"，我们可以分割为[ "aa","b" ]，这只需要一次切割（在"aa"和"b"之间切割），所以最小切割数为1。注意，如果字符串本身已经是回文串，则最小切割数为0。 这是一个典型的线性动态规划问题，通常称为"回文分割"(Palindrome Partitioning)的变种，但更精确地说是"回文分割 II"(Palindrome Partitioning II)，因为它只要求最少切割数，而不需要列举所有分割方案。 解题过程 这个问题可以分解为两个子问题： 判断字符串的任意子串是否为回文串。 基于回文信息，计算从开头到每个位置的最小切割数。 步骤1：预处理回文信息（构建回文判断表） 为了高效地判断任意子串s[ i..j]（0 ≤ i ≤ j < n）是否为回文串，我们使用一个二维布尔数组 isPal[i][j] ，其中 isPal[i][j] 为真表示子串s[ i..j ]是回文串。 构建这个表也使用动态规划，其状态转移基于以下观察： 单个字符是回文串： isPal[i][i] = true 。 两个相同字符是回文串： isPal[i][i+1] = (s[i] == s[i+1]) 。 对于长度大于2的子串， isPal[i][j] 为真当且仅当 s[i] == s[j] 且 isPal[i+1][j-1] 为真。 我们可以按子串长度递增的顺序填充这张表。 步骤2：计算最小切割数 定义 dp[i] 为子串s[ 0..i]（前i+1个字符）分割成若干回文子串所需的最小切割数。我们的目标是求 dp[n-1] 。 状态转移思路： 如果子串s[ 0..i]本身就是回文串，那么不需要切割， dp[i] = 0 。 否则，我们需要在某个位置j（0 ≤ j < i）之后切一刀，将s[ 0..i]分成两部分：s[ 0..j]和s[ j+1..i]。其中s[ j+1..i]必须是回文串（因为最后一刀切出来的最后一段必须是回文串），而s[ 0..j]部分的最小切割数就是 dp[j] 。那么总切割数就是 dp[j] + 1 （在j之后切一刀）。我们需要遍历所有可能的j，取最小值。 状态转移方程： 同时，如果整个s[ 0..i]是回文串， dp[i] 可以直接为0。 步骤3：边界情况与初始化 当i=0时，只有一个字符，它是回文串，所以 dp[0] = 0 。 在计算 dp[i] 时，我们也可以考虑j = -1的情况，这对应于将s[ 0..i ]整体作为一段（即不切），但前提是它是回文串，我们已经单独处理了。 为了处理j = -1的情况，我们可以将 dp 数组的长度设为n，并让 dp[i] 表示子串s[ 0..i]的最小切割数。在状态转移中，如果j = -1，意味着我们考虑s[ 0..i]本身是回文串，此时 dp[-1] 应该为-1（因为切割前一段的切割数为0，但切割次数为0，所以 dp[j] + 1 应为0）。我们可以通过初始化 dp[i] 为一个较大值（如i，因为最多切i刀），然后单独判断 s[0..i] 是否为回文串来简化。 步骤4：算法流程 初始化n = s.length()。 创建二维布尔数组 isPal[n][n] ，全部初始化为false。 填充 isPal ： 对于长度=1： isPal[i][i] = true 。 对于长度=2： isPal[i][i+1] = (s[i] == s[i+1]) 。 对于长度len从3到n： 对于i从0到n-len： j = i + len - 1 isPal[i][j] = (s[i] == s[j] && isPal[i+1][j-1]) 创建一维数组 dp[n] ， dp[i] 初始化为i（因为最多切i刀，将每个字符单独切出）。 对于每个i从0到n-1： 如果 isPal[0][i] 为真，则 s[0..i] 本身是回文串， dp[i] = 0 。 否则，对于每个j从0到i-1： 如果 isPal[j+1][i] 为真（即s[ j+1..i]是回文串），则 dp[i] = min(dp[i], dp[j] + 1) 。 返回 dp[n-1] 。 步骤5：复杂度分析 时间复杂度：填充 isPal 表需要O(n²)，计算 dp 需要两层循环，也是O(n²)。总时间复杂度为O(n²)。 空间复杂度： isPal 表需要O(n²)空间， dp 数组需要O(n)空间。总空间复杂度为O(n²)。但我们可以优化空间，例如在计算 dp 时实时计算回文，但会牺牲时间，这里不展开。 示例 以s = "aab"为例： 构建 isPal 表： "a": (0,0)=true, (1,1)=true, (2,2)=true "aa": (0,1)=true "ab": (1,2)=false "aab": (0,2): s[ 0]=='a', s[ 2 ]=='b'，不相等，false。 计算 dp ： i=0: s[ 0..0]="a"是回文，dp[ 0 ]=0。 i=1: s[ 0..1]="aa"是回文，dp[ 1 ]=0。 i=2: s[ 0..2 ]="aab"不是回文。 检查j=0: s[ 1..2 ]="ab"不是回文，跳过。 检查j=1: s[ 2..2]="b"是回文，dp[ 1]=0，所以候选为0+1=1。dp[ 2 ]初始为2，更新为1。 最终dp[ 2 ]=1，即最少切割1次。 这个解法清晰地展示了如何将问题分解为回文判断和最小切割两个动态规划步骤，逐步构建解决方案。