区间动态规划例题：最小涂色次数问题（分段染色最小成本，相邻段颜色可相同但代价不同） 题目描述 给定一个长度为 n 的数组 colors ，表示一排连续段的目标颜色，颜色用整数表示。你每次可以选择一个区间 [i, j] 进行一次涂色操作，将该区间内所有段染成同一种颜色 c ，但操作的代价是固定的 cost 。然而，如果相邻段在涂色后的颜色相同，它们会合并成一个更长的段，并且你之后不能再单独对合并后的子区间进行染色（即染色必须覆盖整个合并后的段）。求将所有段染成目标颜色的最小总代价。 更形式化 ： 初始时，每个位置是一个独立的段。每次操作选择一段连续的位置（一个区间），将其染成颜色 c ，代价为 cost 。如果操作后相邻段颜色相同，它们会立即合并。最终要使得每个位置的颜色等于 colors[i] 。求最小总代价。 循序渐进解题过程 步骤1：问题理解与重述 我们有一排 n 个位置，初始每个位置是一个独立的段，但初始颜色未定义（或认为无色）。 每次操作选择一个区间 [l, r] 和一个颜色 c ，将该区间内所有位置染成颜色 c ，代价为固定值 cost （这里假设 cost 与颜色和区间长度无关，为常数）。 染色后，如果相邻段颜色相同，它们会自动合并，后续染色必须覆盖整个合并段。 目标：用若干次操作，使得最终每个位置 i 的颜色等于 colors[i] 。 问最小总操作次数（因为每次代价相同，等价于最小操作次数）。 实际上这是一个经典的“涂色”区间DP问题，类似“奇怪的打印机”但更简化：因为每次涂色代价固定，我们只最小化操作次数。 关键观察 ： 如果我们要得到最终的颜色序列，最优策略中，最后一次涂色必然覆盖一个完整区间，且这个区间的颜色就是最终这个区间内所有位置的目标颜色。 如果最终区间 [i, j] 的目标颜色都一样，我们可以一次涂成这个颜色。 如果最终区间内颜色不同，我们需要分段涂色，但要注意合并效应。 步骤2：状态定义 定义 dp[i][j] 表示将区间 [i, j] 染成最终目标颜色（即 colors[i..j] ）的最小操作次数。 最终答案： dp[0][n-1] 。 步骤3：状态转移分析 考虑区间 [i, j] ： 情况1 ：如果 colors[i] == colors[j] ，即区间左右两端目标颜色相同。 我们可以先涂整个区间为 colors[i] （一次操作），但这样可能会把中间也涂成这个颜色，如果中间的目标颜色不同，我们需要在后面覆盖。 但有一个更优策略：先涂区间 [i, j] 为 colors[i] ，再处理中间部分。但这样中间部分在涂色时会覆盖掉原来的颜色，可能需要更多操作。 实际上，如果 colors[i] == colors[j] ，我们可以考虑将 i 和 j 放在同一次涂色操作中完成，因为最终它们颜色相同，可以在某次操作中一起涂。 更高效的做法是： 我们可以先涂区间 [i, j] 为 colors[i] （一次操作），然后只需处理 (i, j) 区间内那些不等于 colors[i] 的位置，但这样可能会浪费，因为中间可能有些位置已经是 colors[i] 了，但会被覆盖再涂回来。 但注意：如果我们先涂 [i, j] 为 colors[i] ，那么中间如果颜色不同，我们需要在后续涂色中覆盖它们，覆盖时可能会把 colors[i] 也改掉，导致 i 或 j 的颜色被改变，所以需要在最后再涂一次 colors[i] 吗？这可能导致多余操作。 正确策略 （类似“奇怪的打印机”）： 最优解中，第一次涂区间 [i, j] 时，涂的颜色是 colors[i] （也可以是 colors[j] ），这次操作会将 i 位置的颜色确定下来。之后，我们可以在区间内找一个 k ，使得 colors[k] == colors[i] ，然后将区间分成两段： [i+1, k-1] 和 [k, j] ，但要注意合并规则。 实际上，更简单的转移： 如果 colors[i] == colors[j] ，那么我们可以将 i 和 j 在同一次操作中完成（即某次涂色覆盖了 i 和 j 且颜色为 colors[i] ）。为了最小化操作，我们可以让 dp[i][j] = dp[i][j-1] ，因为在涂好 [i, j-1] 时， j 位置可能已经和 i 在同一次涂色中被覆盖了，所以不需要额外操作。但这是不一定的，因为 j 可能单独涂。 标准转移方程 （基于区间DP常见解法）： 单独涂左端点 i ：一次操作涂区间 [i, i] 为 colors[i] ，然后处理 [i+1, j] ，即 dp[i][j] = 1 + dp[i+1][j] 。 如果在 [i+1, j] 中存在一个位置 k ，使得 colors[k] == colors[i] ，那么我们可以将 i 和 k 在同一次涂色中完成： 先涂区间 [i, k] 为 colors[i] （一次操作），此时 [i, k] 颜色相同，合并成一个段。 然后分别处理 [i+1, k-1] 和 [k+1, j] 。但注意，涂完 [i, k] 后， [i+1, k-1] 已经被覆盖成 colors[i] ，如果它们的目标颜色不是 colors[i] ，我们需要在后续覆盖，这正好是 dp[i+1][k-1] 的任务。而 [k+1, j] 是独立的。 但更优的方式是：先处理 [i+1, k-1] 和 [k+1, j] ，然后在最后一次涂色中同时涂 i 和 k ？不，因为涂色会覆盖区间。 实际上，正确的DP方程是： dp[i][j] = min( dp[i+1][j] + 1, min{ dp[i+1][k-1] + dp[k][j] 其中 colors[i] == colors[k] }) 解释： 第一种：单独涂 i 一次，然后处理 [i+1, j] 。 第二种：找一个 k 在 [i, j] 且 colors[k] == colors[i] ，我们可以在涂 k 的时候顺便涂 i （即涂区间 [i, k] ），那么问题分解为：先处理 [i+1, k-1] （因为 i 和 k 同色，中间部分可以先处理好，再涂 [i, k] ），然后处理 [k, j] 。但注意，处理 [k, j] 时， k 的颜色已经是目标色，所以是 dp[k][j] 。 但更准确是： dp[i][j] = dp[i+1][k-1] + dp[k][j] ，当 colors[i] == colors[k] ，且 k 在 [i+1, j] 。 为什么？因为我们可以先处理 [i+1, k-1] 得到正确颜色，然后一次操作涂 [i, k] 为 colors[i] ，这样 i 和 k 都对了，然后处理 [k+1, j] ，但注意 [k+1, j] 是独立的，即 dp[k][j] 已经包含了 k 位置的颜色正确处理。 步骤4：明确转移方程 设 dp[i][j] 为将区间 [i, j] 染好的最小操作数。 基础： dp[i][i] = 1 ，因为只需一次涂色。 转移： a) 单独涂左端点： dp[i][j] = dp[i+1][j] + 1 。 b) 枚举 k = i+1 到 j ，如果 colors[i] == colors[k] ，则 dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) 。 解释：先处理 [i+1, k-1] ，然后一次涂色操作将 [i, k] 涂成 colors[i] ，此时 i 和 k 都正确，再处理 [k, j] 。注意这里 dp[k][j] 表示从 k 到 j 的最小操作，且假设 k 的颜色已经是目标色，所以不需要额外为 k 涂色。 为什么这是正确的 ： 因为 colors[i] == colors[k] ，我们可以在涂 k 的时候把 i 一起涂了，所以 i 不需要单独涂。 dp[i+1][k-1] 是中间部分， dp[k][j] 是右侧部分。涂 [i, k] 的操作已经包含在 dp[k][j] 的第一次涂色中吗？不一定，所以我们需要确保 dp[k][j] 的涂色不会影响 i 。实际上，我们假设涂 [i, k] 是单独一次操作，这次操作应该是在 [i+1, k-1] 和 [k, j] 都处理好之后进行的，但这样就不是DP的子问题。 更准确的解释：我们考虑最后一次涂色覆盖了位置 i ，同时这个涂色也覆盖了某个 k （ k>i 且颜色相同），那么在这次涂色之前，区间 [i+1, k-1] 必须已经涂好（否则会被覆盖），而区间 [k, j] 可以之后涂（因为涂 [i, k] 会影响 k 的颜色，所以 [k, j] 必须在涂 [i, k] 之后处理）。但这样顺序是先处理 [i+1, k-1] ，然后涂 [i, k] ，然后处理 [k+1, j] 。 因此方程应为： dp[i][j] = min( dp[i+1][k-1] + 1 + dp[k+1][j] ) 当 colors[i] == colors[k] 。 但这样没有利用 k 位置已经在涂 [i, k] 时涂好，所以 dp[k+1][j] 是独立的。 常见正确方程 （类似“奇怪的打印机”）： dp[i][j] = min( dp[i+1][j] + 1, min{ dp[i+1][k-1] + dp[k][j] for k in [i+1, j] if colors[i] == colors[k] }) 。 这个方程是经典解法，其正确性基于：当 colors[i] == colors[k] ，我们可以将 i 和 k 放在同一次涂色中完成，那么涂色区间至少是 [i, k] 。在最优解中，这次涂色发生在处理完 [i+1, k-1] 之后，并且处理 [k, j] 时， k 的颜色已经正确，所以 [k, j] 的问题就是子问题 dp[k][j] 。 步骤5：递推顺序 区间长度从小到大计算： len = 1 to n ， i = 0 to n-len ， j = i+len-1 。 步骤6：初始化 dp[i][i] = 1 。 步骤7：示例验证 例子： colors = [1, 2, 1, 2] ， n=4 。 计算： len=1 : dp[0][0]=1 , dp[1][1]=1 , dp[2][2]=1 , dp[3][3]=1 。 len=2 : [0,1] : colors[ 0]!=colors[ 1]， dp[0][1]=min(dp[1][1]+1=2, 无k)=2 。 [1,2] : colors[ 1]!=colors[ 2]， dp[1][2]=dp[2][2]+1=2 。 [2,3] : colors[ 2]!=colors[ 3]， dp[2][3]=dp[3][3]+1=2 。 len=3 : [0,2] : colors[ 0]==colors[ 2]=1， k=2 ， dp[0][2]=min(dp[1][2]+1=3, dp[1][1]+dp[2][2]=1+1=2) = 2 。 [1,3] : colors[ 1]==colors[ 3]=2， k=3 ， dp[1][3]=min(dp[2][3]+1=3, dp[2][2]+dp[3][3]=1+1=2) = 2 。 len=4 : [0,3] : colors[ 0]!=colors[ 3]， dp[0][3]=min(dp[1][3]+1=3, ...) 。 检查 k ： k=2 时 colors[ 0]==colors[ 2]=1， dp[0][3]=min(3, dp[1][1]+dp[2][3]=1+2=3)=3 。 所以最小操作数=3。 实际最优操作： 涂 [ 0,2 ] 为颜色1（一次）。 涂 [ 1,1 ] 为颜色2（一次）。 涂 [ 3,3 ] 为颜色2（一次）。 总共3次。正确。 步骤8：算法复杂度 状态数 O(n²)，转移枚举 k O(n)，总 O(n³)。空间 O(n²)。 步骤9：核心思想总结 本题的关键点是：如果区间左右端点目标颜色相同，我们可以通过一次涂色同时完成它们，从而减少操作次数。转移时枚举与左端点同色的位置，将区间分段处理，利用子问题最优解。这是区间DP中常见的“涂色”类问题的一种变体。