区间动态规划例题：回文分割的最小切割次数问题 题目描述 给定一个字符串 s ，要求将 s 分割成若干个子串，使得每个子串都是回文串。问最少需要多少次切割才能达到要求？ 例如： 输入： s = "aab" 输出： 1 解释：只需切割一次，将字符串分割为 ["aa", "b"] ，两个子串都是回文串。 解题思路 1. 问题分析 我们需要将字符串分割成多个回文子串，且切割次数最少。关键在于判断任意子串 s[i..j] 是否为回文，并找到最优的分割点。 2. 动态规划状态定义 定义 dp[i] 表示子串 s[0..i] （前 i+1 个字符）的最小切割次数。目标是求 dp[n-1] （n 为字符串长度）。 3. 预处理回文信息 为了快速判断任意子串是否为回文，使用动态规划预处理一个二维数组 isPal[i][j] ，表示 s[i..j] 是否为回文： 初始条件：单个字符是回文（ isPal[i][i] = true ），相邻相同字符是回文（ isPal[i][i+1] = true 若 s[i] == s[i+1] ）。 状态转移： isPal[i][j] = true 当且仅当 s[i] == s[j] 且 isPal[i+1][j-1] = true （i+1 ≤ j-1）。 4. 主动态规划转移方程 对于每个位置 j （0 ≤ j < n）： 如果 s[0..j] 本身是回文（即 isPal[0][j] == true ），则不需要切割： dp[j] = 0 。 否则，遍历所有可能的分割点 i （0 ≤ i < j）： 如果 s[i+1..j] 是回文（ isPal[i+1][j] == true ），则可以在 i 处切割，将问题转化为 s[0..i] 的最小切割次数加上本次切割： dp[j] = min(dp[j], dp[i] + 1) 。 5. 初始化与计算顺序 初始化 dp 数组为一个较大值（如无穷大）， dp[0] = 0 （单个字符无需切割）。 按 j 从 0 到 n-1 顺序计算 dp[j] ，同时预处理 isPal 时需按子串长度从小到大计算。 示例演示 以 s = "aab" 为例： 预处理 isPal ： 长度1： (0,0)=T , (1,1)=T , (2,2)=T 长度2： (0,1)=T （"aa"）, (1,2)=F （"ab"） 长度3： (0,2)=F （"aab" 不是回文） 计算 dp ： j=0 ： s[0..0]="a" 是回文， dp[0]=0 j=1 ： s[0..1]="aa" 是回文， dp[1]=0 j=2 ： s[0..2] 不是回文，尝试分割点： i=0 ：检查 s[1..2]="ab" 不是回文，跳过 i=1 ：检查 s[2..2]="b" 是回文， dp[2] = min(∞, dp[1]+1) = 1 最终 dp[2] = 1 复杂度分析 时间复杂度：O(n²)，预处理 isPal 和计算 dp 均为双重循环。 空间复杂度：O(n²)，存储 isPal 矩阵。可优化至 O(n) 但会增加时间复杂度。