区间动态规划例题：最小涂色次数问题（进阶版） 题目描述： 给定一个长度为 n 的字符串 s，表示一排需要涂色的格子。每次操作可以选择一个连续的区间，并将该区间内所有格子涂成同一种颜色（覆盖原有颜色）。但有一个特殊规则：如果选择的区间两端颜色相同，那么这次操作的成本为 1；如果两端颜色不同，成本为 2。求将整排格子涂成目标颜色串 s 所需的最小总成本。 解题过程： 问题分析：这是一个典型的区间动态规划问题。我们需要找到一种涂色顺序，使得总成本最小。关键观察是：如果区间两端的颜色相同，我们可以先一次性涂整个区间（成本1），然后再处理内部细节。 状态定义：定义 dp[ i][ j] 表示将区间 [ i, j ] 涂成目标颜色所需的最小成本。 状态转移方程： 基础情况：当 i == j 时，只需要一次操作，成本为 1，即 dp[ i][ i ] = 1 对于区间 [ i, j ]： 如果 s[ i] == s[ j]：我们可以先花成本1涂整个区间为 s[ i ] 的颜色，然后处理内部 dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 解释：因为两端颜色相同，涂整个区间的成本与只涂左端或右端再扩展是一样的 如果 s[ i] != s[ j ]：我们需要分别处理左右两部分 dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j ])，其中 k 从 i 到 j-1 解释：将区间分成两个子区间分别处理，然后合并成本 具体计算步骤： 以字符串 "aabaa" 为例： 初始化所有长度为1的区间：dp[ 0][ 0]=1, dp[ 1][ 1]=1, ..., dp[ 4][ 4 ]=1 计算长度为2的区间： [ 0,1]：s[ 0]=='a' == s[ 1]=='a'，dp[ 0][ 1] = min(dp[ 1][ 1], dp[ 0][ 0 ]) = min(1,1) = 1 [ 1,2]：s[ 1]=='a' != s[ 2]=='b'，dp[ 1][ 2] = min(dp[ 1][ 1]+dp[ 2][ 2 ]) = 1+1 = 2 继续计算更长的区间，直到整个字符串 [ 0,4 ] 算法优化：在计算过程中，我们可以使用记忆化搜索或自底向上的填表法，确保每个子区间只计算一次。 时间复杂度：O(n³)，空间复杂度：O(n²)，其中 n 是字符串长度。 这个问题的核心在于理解：当区间两端颜色相同时，我们可以用更低的成本完成涂色，这体现了区间动态规划中利用子问题最优解来构建原问题解的思想。