区间动态规划例题：最小涂色次数问题（字符替换、相邻同色可合并版） 题目描述 给你一个字符串 s ，长度为 n ，由大写字母组成。每次操作，你可以： 选择一个位置，将该位置的字符替换成任意一个大写字母（替换操作）。 在替换后，如果出现相邻的两个字符相同，它们会立即合并成一个字符（即字符串长度减少）。 你的目标是通过若干次操作，使得字符串最终变成一个回文串。问最少需要进行多少次替换操作。 示例 输入： s = "ABAC" 输出： 1 解释：将第三个字符 'A' 替换为 'B' ，字符串变为 "ABBC" ，合并相邻相同字符 'B' 后成为 "ABC" ，再将第二个字符 'B' 替换为 'A' 得到 "AAC" ，合并后变为 "AC" ，不是回文。另一种方案：将第一个字符 'A' 替换为 'C' ，得到 "CBAC" ，合并后为 "CBAC" ，再将第四个字符 'C' 替换为 'B' 得 "CBAB" ，合并后为 "CBAB" ，仍不是回文。实际上，最佳方案是将第三个字符 'A' 替换为 'C' ，得到 "ABCC" ，合并相邻 'C' 后为 "ABC" ，再将第二个字符 'B' 替换为 'A' 得到 "AAC" ，合并后为 "AC" ，非回文。再尝试：将第四个字符 'C' 替换为 'A' ，得到 "ABAA" ，合并相邻 'A' 后为 "ABA" ，此时已是回文，仅用 1 次替换。 约束条件 1 <= n <= 200 字符串只包含大写字母。 解题思路 本题融合了字符替换、相邻合并和回文构造，关键在于如何处理“合并”这一动态变化。我们可以从区间动态规划的角度思考： 定义状态： dp[i][j] 表示将子串 s[i..j] 通过替换和合并操作变成回文串所需的最少替换次数。 最终答案： dp[0][n-1] 。 状态转移需要考虑合并的影响，特别是当子串两端字符在操作后可能因合并而与内部字符作用。 核心难点 合并操作会导致字符消失，从而改变区间边界。例如， "AA" 合并后变成 "A" ，相当于区间长度减少。因此在规划时，我们需考虑子串经过操作后，其首尾字符可能并非原字符，而是经过合并后的结果。 解决思路 我们可以将合并操作隐式处理： 如果 s[i] == s[j] ，且它们各自不与相邻字符合并，则两端已匹配，只需处理内部 dp[i+1][j-1] 。 但更一般地，我们考虑将子串划分成两部分，分别处理，并在划分点允许字符合并。 更通用的定义 定义 dp[l][r] 表示将子串 s[l..r] 变成 空串或单字符 （即最终可合并成一个回文单元）所需的最少替换次数。但这样定义难以直接得到最终回文（因为最终可能是多个字符的回文）。实际上，最终回文串的每个字符都对应原串中某个连续段合并而成。因此，我们可以将问题转化为：将原串划分成若干连续段，每段通过替换和合并最终变成一个字符，且这些字符构成回文。 更精确的状态 定义 dp[l][r] 表示将子串 s[l..r] 通过操作变成 一个字符 所需的最少替换次数。那么整个串要变成回文，相当于要将原串划分成若干个不相交的连续段，每段各自合并成一个字符，且这些字符构成回文。 但这样仍复杂，因为段与段之间独立，且回文要求对称段字符相同。 标准区间DP解法 常见方法是扩展状态： dp[l][r] 表示将 s[l..r] 变成回文串所需最少替换次数，但合并操作隐含在状态转移中。转移时考虑： 如果 s[l] 和 s[r] 最终能匹配（即经过替换和合并后相同），则问题转化为 dp[l+1][r-1] 加上将 s[l] 和 s[r] 变成相同字符的替换代价。 但 s[l] 或 s[r] 可能和相邻字符合并，因此我们需枚举 l 向右合并的长度和 r 向左合并的长度。 这会导致复杂度较高。一种简化思路是： 每次操作可以替换一个字符，替换后立即合并所有相邻相同字符。 我们可以将合并过程视为：连续相同字符段可视为一个整体（因为合并后会变成一个字符）。 更简洁的解法 先将原串进行“游程编码”，即合并连续相同字符为一个块，每个块记录字符和长度。例如 "ABAC" → 块序列： ('A',1) , ('B',1) , ('A',1) , ('C',1) 。但本题中替换字符可能导致块合并，所以不能简单预处理。 常见题解采用的状态设计 定义 dp[l][r] 表示将子串 s[l..r] 变成回文串的最少替换次数，转移时： 如果 s[l] == s[r] ，则可以不替换两端，直接由 dp[l+1][r-1] 转移而来。 否则，可以替换 s[l] 或 s[r] 使其与另一端相等，然后考虑合并可能影响相邻字符。 但这样仍不够，因为替换后合并可能导致区间缩短。因此，更通用的转移是： 考虑子串的第一个字符最终和哪个位置的字符匹配（可能是经过合并后的同字符段）。我们可以枚举与 l 匹配的位置 k （ l <= k <= r ），使得 s[l..k] 这一段最终合并成一个字符，且这个字符与右边某段匹配。 更可行的状态 定义 dp[l][r] 表示将子串 s[l..r] 变成回文串的最少替换次数，转移考虑两种情形： 情形1： s[l] 不与其他字符合并（即它单独作为一个字符留在最终回文中），那么它需要和右边的某个字符匹配（该字符可能是原串中某个位置经过合并后形成的）。为匹配，我们可以将 s[l] 替换为某个字符 ch ，并在右边找一个字符也变成 ch ，然后中间部分单独处理。但这样需要枚举右边匹配位置，复杂度高。 情形2： s[l] 和它右边的字符（比如 l+1 ）合并，那么我们需要将 s[l] 替换成与 s[l+1] 相同，然后合并，这相当于用一次替换将 l 和 l+1 合并，然后处理新区间。 实际采用的动态规划方程 设 dp[l][r] 表示将子串 s[l..r] 变成回文串的最少替换次数。 转移方程： 如果 l == r ，已经是回文，不需要替换， dp[l][r] = 0 。 否则，考虑对 s[l] 的操作： a) 不替换 s[l] ，也不与右边合并：则它需要和右边某个位置匹配。但这样不好直接处理。 b) 替换 s[l] 为某个字符，可能引发合并。 更常见且简单的解法思路 将替换和合并操作拆解： 每次操作：选择一个位置，改变字符，然后立即合并所有相邻相同字符。 目标：使最后字符串是回文。 观察到，最终回文的每个字符对应原串的一个连续段（该段内所有字符相同，因为合并会使它们相同）。因此，问题等价于：将原串划分成若干连续段，每段内字符相同（可通过替换实现），且这些段按顺序对称相等。 这可以转化为区间DP： dp[l][r] 表示将 s[l..r] 变成回文的最少替换次数。 转移： 如果 s[l] == s[r] ，则两端已相等，可以直接由 dp[l+1][r-1] 转移。 否则，可以尝试将左端或右端替换成另一端字符，但替换后可能引发合并，从而改变区间边界。 一种正确的状态转移 定义 dp[l][r] 为将子串 s[l..r] 变成回文的最少替换次数。 考虑左端字符 s[l] ，它最终会与右端的某个字符匹配（可能经过合并）。我们可以枚举与 l 匹配的位置 k （ k 在 l 到 r 之间），使得 s[l..k] 这一段最终合并成一个字符，并且这个字符与右边某段匹配。但这样需要二维枚举，复杂度 O(n³)。 优化转移 注意到，如果我们希望 s[l] 和 s[r] 匹配，且 s[l] != s[r] ，则至少需要一次替换（将其中一个变成另一个）。替换后，如果被替换的字符与相邻字符相同，会合并，导致区间缩短。但我们可以先处理内部，再考虑两端匹配。 最终采用的经典方程 设 dp[l][r] 表示将子串 s[l..r] 变成回文的最少替换次数。 转移： 如果 s[l] == s[r] ，则 dp[l][r] = dp[l+1][r-1] 。 否则， dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + 1 。 但这是不考虑合并的情况。考虑合并后，如果我们将 s[l] 替换成与 s[l+1] 相同，则 l 和 l+1 合并，相当于用一次替换操作将区间变为 [l+1, r] 的情况，即 dp[l][r] = min(dp[l][r], 1 + dp[l+1][r]) 。同理，右端合并： dp[l][r] = min(dp[l][r], 1 + dp[l][r-1]) 。 这实际与上式相同。 考虑合并的更精细情况 如果 s[l] == s[l+1] ，则它们本已相同，合并不需要替换，所以 dp[l][r] = min(dp[l][r], dp[l+1][r]) 。 同理，如果 s[r] == s[r-1] ，则 dp[l][r] = min(dp[l][r], dp[l][r-1]) 。 一般性转移 综合以上，我们得到： 基础情况： l >= r 时， dp[l][r] = 0 。 转移1：如果 s[l] == s[r] ， dp[l][r] = min(dp[l][r], dp[l+1][r-1]) 。 转移2：考虑将 s[l] 替换成与 s[l+1] 相同（如果本来相同则无需替换），然后合并，则 dp[l][r] = min(dp[l][r], cost + dp[l+1][r]) ，其中 cost = 0 if s[l] == s[l+1] else 1 。 转移3：考虑将 s[r] 替换成与 s[r-1] 相同，然后合并，则 dp[l][r] = min(dp[l][r], cost + dp[l][r-1]) ，其中 cost = 0 if s[r] == s[r-1] else 1 。 转移4：考虑将 s[l] 替换成与 s[r] 相同（如果本来相同则无需替换），然后如果 l+1 <= r-1 ，则两端可能合并中间部分，但更一般的情况是：替换后若 s[l] 变成与 s[r] 相同，则它们可能直接匹配，中间部分需处理，即 dp[l][r] = min(dp[l][r], cost + dp[l+1][r-1]) ，其中 cost = 0 if s[l] == s[r] else 1 。 实际上，转移2、3是转移4的特例（当一端与相邻字符匹配时）。 标准解法 经过整理，标准解法为： dp[l][r] 初始为 INF。 如果 s[l] == s[r] ， dp[l][r] = min(dp[l][r], dp[l+1][r-1]) 。 否则， dp[l][r] = min(dp[l][r], 1 + dp[l+1][r-1]) （将一端替换成另一端）。 dp[l][r] = min(dp[l][r], 1 + dp[l+1][r]) （将左端替换成某个字符，使其与右部合并，但这里简化为一次替换后，左端消失）。 dp[l][r] = min(dp[l][r], 1 + dp[l][r-1]) （将右端替换成某个字符，使其与左部合并）。 合并相邻相同字符的情况已隐含在上述转移中 ，因为当 s[l] == s[l+1] 时，自然有 dp[l+1][r] 已考虑合并。 示例验证 s = "ABAC" ，n=4。 计算： dp[ 0][ 3]：s[ 0]='A', s[ 3 ]='C'，不相等。 选项： a) 1+dp[ 1][ 2] = 1+dp[ 1][ 2]。需先算 dp[ 1][ 2]：s[ 1]='B', s[ 2 ]='A'，不相等。 dp[ 1][ 2] 选项：1+dp[ 2][ 2]=1, 1+dp[ 1][ 1]=1, 1+dp[ 2][ 2 ]=1（两端替换），取最小值 1。 所以 1+1=2。 b) 1+dp[ 0][ 2] = 1+dp[ 0][ 2]。dp[ 0][ 2]：s[ 0]='A', s[ 2]='A'，相等，所以 dp[ 0][ 2]=dp[ 1][ 1 ]=0。则 1+0=1。 c) 1+dp[ 1][ 3] = 1+dp[ 1][ 3]。dp[ 1][ 3]：s[ 1]='B', s[ 3 ]='C'，不相等。 dp[ 1][ 3] 选项：1+dp[ 2][ 2]=1, 1+dp[ 1][ 2]=1+1=2, 1+dp[ 2][ 3]（需计算 dp[ 2][ 3]：s[ 2]='A',s[ 3]='C'，不相等，dp[ 2][ 3]=min(1+dp[ 3][ 3],1+dp[ 2][ 2],1+dp[ 3][ 3]?)。具体计算：dp[ 2][ 3] 两端不等，1+dp[ 3][ 2]无效，实际 dp[ 2][ 3 ]=1（替换一端），所以 1+1=2。 所以 dp[ 1][ 3 ] 最小为 1，则 1+1=2。 取最小为 1。 所以 dp[ 0][ 3 ]=1，与示例一致。 算法步骤 初始化 dp[n][n] 为 0。 按区间长度从 2 到 n 遍历： 对于每个区间 [ l, r ]： a) 设初值为 INF。 b) 如果 s[ l] == s[ r]， dp[l][r] = dp[l+1][r-1] 。 c) 否则， dp[l][r] = 1 + dp[l+1][r-1] 。 d) dp[l][r] = min(dp[l][r], 1 + dp[l+1][r]) 。 e) dp[l][r] = min(dp[l][r], 1 + dp[l][r-1]) 。 输出 dp[0][n-1] 。 时间复杂度 O(n²)，因为每个状态转移是 O(1)。 小结 本题通过区间DP，将合并操作隐含在状态转移中，关键点在于考虑两端字符的匹配和合并情况，通过三种转移覆盖所有可能操作。