区间动态规划例题：回文分割的最小切割次数问题 题目描述 给定一个字符串 s ，要求将 s 分割成若干个子串，使得每个子串都是回文串。求最少需要几次切割才能实现这样的分割。 例如： 输入 s = "aab" ，可以分割为 ["aa","b"] ，需要 1 次切割。 输入 s = "a" ，不需要切割，输出 0。 输入 s = "ab" ，可以分割为 ["a","b"] ，需要 1 次切割。 解题思路 问题分析 目标是找到最少的切割次数，使得所有子串都是回文。 若整个字符串本身是回文，则切割次数为 0。 若某子串 s[i:j] 是回文，则可以在 j 处切割，问题转化为对剩余部分 s[j+1:] 进行分割。 动态规划定义 设 dp[i] 表示子串 s[0:i] （长度为 i ）的最小切割次数。 最终目标是求 dp[n] （ n 为字符串长度）。 状态转移 遍历每个位置 i ，尝试所有可能的回文前缀 s[j:i] （其中 0 ≤ j < i ）： 若 s[j:i] 是回文，则可以在 j 处切割，此时 dp[i] = min(dp[i], dp[j] + 1) 。 初始条件： dp[0] = -1 （空串不需要切割，但为了统一计算，设为基础值）。 回文判断优化 预处理二维数组 isPal[i][j] ，表示 s[i:j+1] 是否为回文，避免重复计算。 利用动态规划填充 isPal ： 单个字符是回文。 两个相同字符是回文。 若 s[i] == s[j] 且 isPal[i+1][j-1] 为真，则 isPal[i][j] 为真。 详细步骤 初始化 n = len(s) dp = [float('inf')] * (n+1) dp[0] = -1 isPal = [[False] * n for _ in range(n)] 预处理回文表 遍历所有子串长度 len 从 1 到 n ： 遍历起点 i 从 0 到 n-len ： j = i + len - 1 若 len == 1 ， isPal[i][j] = True 若 len == 2 ， isPal[i][j] = (s[i] == s[j]) 否则， isPal[i][j] = (s[i] == s[j] and isPal[i+1][j-1]) 动态规划计算最小切割 遍历 i 从 1 到 n ： 遍历 j 从 0 到 i-1 ： 若 isPal[j][i-1] 为真（即 s[j:i] 是回文）： dp[i] = min(dp[i], dp[j] + 1) 返回结果 最终 dp[n] 即为答案。 示例演算 以 s = "aab" 为例： 预处理 isPal ： 长度为1： (0,0)=T, (1,1)=T, (2,2)=T 长度为2： (0,1)=（a==a?）T, (1,2)=（a==b?）F 长度为3： (0,2)=（a==b? 且 isPal[1][1]=T）F 计算 dp ： i=1 ： j=0 ， s[0:1]="a" 是回文， dp[1] = min(inf, dp[0]+1) = 0 i=2 ： j=0 ： s[0:2]="aa" 是回文， dp[2] = min(inf, dp[0]+1) = 0 j=1 ： s[1:2]="a" 是回文， dp[2] = min(0, dp[1]+1=1) = 0 i=3 ： j=0 ： s[0:3]="aab" 不是回文，跳过 j=1 ： s[1:3]="ab" 不是回文，跳过 j=2 ： s[2:3]="b" 是回文， dp[3] = min(inf, dp[2]+1) = 1 结果： dp[3] = 1 复杂度分析 时间复杂度：O(n²)（预处理回文表 O(n²)，动态规划 O(n²)） 空间复杂度：O(n²)（存储回文表） 通过以上步骤，即可高效求出将字符串分割为回文子串的最小切割次数。