区间动态规划例题：最小涂色次数问题（分段染色最小成本，相邻段颜色可相同但代价不同，环形版本）
字数 5038 2025-12-15 10:58:58

区间动态规划例题：最小涂色次数问题（分段染色最小成本，相邻段颜色可相同但代价不同，环形版本）

题目描述

你有一个环形序列，由 \(n\) 个连续段组成，每个段可以染成 \(m\) 种颜色之一。染色规则如下：

  1. 每次染色必须选择环形序列中的一个连续子段（在环上连续），并将其全部染成同一种颜色。
  2. 已染色的段可以被后面的染色覆盖。
  3. 最终目标是要让整个环形序列的第 \(i\) 段颜色为指定目标颜色 \(target[i]\)。
  4. 每次染色的代价是 1（无论染多长的子段，代价固定为 1）。
  5. 特殊约束：在最终染色结果中，如果相邻两段颜色相同，它们被视为同一“颜色段”，并且如果同一颜色段在染色过程中被分多次染色，则每次染色都独立计算代价。但注意，我们最终只关心用最少的总染色次数完成目标颜色序列。

换句话说，我们可以将环形序列按照最终目标颜色分成若干“颜色段”（相邻同色合并），然后问题转化为：用最少染色次数覆盖所有这些颜色段，每次染色覆盖环上一个连续子段，且必须染成同一种颜色（可以和目标颜色不同，但最终必须被覆盖成目标颜色）。求最少染色次数。

输入：

  • 整数 \(n\)，环形序列长度。
  • 数组 \(target[0..n-1]\)，表示每段的目标颜色（用 1~m 表示）。
  • 环形意味着 \(target[n-1]\) 与 \(target[0]\) 相邻。

输出：

  • 最少染色次数。

示例：
环形序列的目标颜色 = [1, 2, 1, 2]（颜色 1 和 2）。
最少染色次数是 3。
解释：
一种染色方案：

  1. 染色整个环为颜色 1。
  2. 染色位置 1 和位置 3 为颜色 2（在环上是不连续的两段，所以必须分开两次染色）。
  3. 总共 3 次。

解题思路

这是一个环形区间 DP 问题，关键在于断环成链，并定义状态表示染色一个区间的最少次数。

第一步：简化问题（将环形转化为线性）

环形的难点在于，染色可以跨过环的起点和终点。
常用的方法是：复制一倍数组，然后枚举断点，转化为线性问题求解。

设线性数组长度为 \(2n\)：

\[\text{newTarget}[i] = target[i \bmod n], \quad i=0..2n-1 \]

我们任取长度为 \(n\) 的一段作为环形展开，但为了处理方便，我们直接考虑在长度为 \(2n\) 的数组上进行区间 DP，然后取所有长度为 \(n\) 的区间中，从初始全未染色状态到染成目标颜色的最少次数。
但实际上，我们初始状态是全未染色（可视为任意颜色，但未确定），每次染色可覆盖成某种颜色，最终必须匹配目标颜色。

第二步：线性问题的状态定义

设 \(dp[l][r]\) 表示将区间 \([l, r]\) 染成目标颜色（即最终颜色与 \(target\) 一致）所需的最少染色次数。
注意：区间 \([l, r]\) 是线性数组的一段（来自展开后的数组），我们要计算染色它的最少次数。

关键观察：

  1. 如果区间内所有目标颜色相同，那么一次染色即可（一次染成这个颜色）。
  2. 如果区间两端的目标颜色相同，则最优策略可能是先染一次将该区间染成这个颜色，然后再处理中间不同颜色的部分。但这样可能不是最优，因为先染中间再覆盖两端可能更好。
    实际上，这是经典的“奇怪的打印机”问题的扩展，只是颜色数量更多，但每次染色代价固定为 1。

“奇怪的打印机”问题的状态转移：

\[dp[l][r] = \begin{cases} 1 & \text{如果 } l = r \\ \min_{l \le k < r} (dp[l][k] + dp[k+1][r]) & \text{一般情况} \\ dp[l][r-1] & \text{如果 } target[l] = target[r] \text{ 且 } l < r \end{cases} \]

但最后一条需要更仔细处理：当 \(target[l] = target[r]\) 时，我们可以在第一次染色时把 \([l, r]\) 染成 \(target[l]\)，然后只需处理中间部分，即 \(dp[l][r] = \min(dp[l][r], dp[l][r-1])\) 吗？
不完全是。在“奇怪的打印机”中，当两端颜色相同时，最优策略可以是第一次染色时覆盖整个区间为这个颜色，然后内部再调整。此时，第一次染色固定了区间颜色，内部调整只需从 \(l\) 到 \(r-1\) 的最小次数（因为右端已对，但可能被中间染色覆盖再重新染回来）。
正确转移：

\[dp[l][r] = \min(dp[l][r-1], dp[l+1][r]) \]

当 \(target[l] = target[r]\) 时，因为第一次染色可以染 \([l, r]\) 为 \(target[l]\)，之后相当于只处理 \([l, r-1]\) 或 \([l+1, r]\)。
更准确的标准“奇怪的打印机”转移：

  • 基础：\(dp[l][r] = 1 + dp[l][r-1]\) 表示先染 \(r\) 位置，再染左边。
  • 当 \(target[k] = target[r]\) 且 \(l \le k < r\) 时，我们可以把区间分成 \([l, k]\) 和 \([k+1, r-1]\)，先染 \([k+1, r]\) 为 \(target[r]\)，然后左边再处理。但这样需要仔细推导。

标准方程（来自 LeetCode 奇怪的打印机）：

\[dp[l][r] = dp[l][r-1] + 1 \]

然后尝试 \(k \in [l, r-1]\)，如果 \(target[k] = target[r]\)，则

\[dp[l][r] = \min(dp[l][r], dp[l][k] + dp[k+1][r-1]) \]

这里 \(dp[k+1][r-1]\) 表示区间 \([k+1, r-1]\) 的次数，因为第 \(k\) 个位置颜色和 \(r\) 相同，可以在同一次染色覆盖。

第三步：环形处理

将数组复制一倍：\(a[0..2n-1]\) 为 \(target[i \bmod n]\)。

我们要求的是环形的答案。环形的最小染色次数，等于在 \(2n\) 数组中选取长度为 \(n\) 的区间的最小染色次数吗？
不完全是，因为环上染色可以跨过复制点。但我们可以这样处理：在环形中，我们可以固定起点为某个颜色段的首个位置，转化为线性问题。
更简单的方法：
在 \(2n\) 数组上做区间 DP 后，环形答案 =

\[\min_{i=0}^{n-1} dp[i][i+n-1] \]

即任取一段长度为 \(n\) 的区间的最小染色次数。

但要注意：我们的 \(dp[l][r]\) 定义是“从白纸状态（或任意初始状态）染成目标颜色的最少次数”，这里初始状态是未染色，每次染色可任意覆盖，所以这个定义是正确的。

第四步：状态转移方程（最终版）

  1. 当 \(l = r\) 时，\(dp[l][r] = 1\)。
  2. 否则：

\[dp[l][r] = dp[l][r-1] + 1 \]

然后遍历 \(k = l\) 到 \(r-1\)：
如果 \(a[k] = a[r]\)，则

\[dp[l][r] = \min(dp[l][r], dp[l][k] + dp[k+1][r-1]) \]

注意：当 \(k = r-1\) 时，\(dp[k+1][r-1]\) 表示空区间，值为 0，所以转移为 \(dp[l][r-2] + 1\) 不对，应直接为 \(dp[l][r-1]\)。

实际上，空区间处理为 0，所以当 \(k = r-1\) 时，转移为 \(dp[l][r-1] + 0\) 与第一种情况相同，不会更优。
所以这个转移覆盖了“两端颜色相同”时的情况。

第五步：算法步骤

  1. 将 \(target\) 数组复制一倍，得到 \(a[0..2n-1]\)。
  2. 初始化 \(dp\) 为 \(2n \times 2n\) 矩阵，\(dp[i][i] = 1\)。
  3. 按区间长度 \(len = 2\) 到 \(2n\)：
    • 遍历起点 \(l\)：
      \(r = l + len - 1\)，如果 \(r \ge 2n\) 则跳出。
      先令 \(dp[l][r] = dp[l][r-1] + 1\)。
      遍历 \(k = l\) 到 \(r-1\)：
      如果 \(a[k] = a[r]\)：
      \(left = dp[l][k]\)
      \(right = 0\) 如果 \(k+1 > r-1\)，否则 \(right = dp[k+1][r-1]\)
      \(dp[l][r] = \min(dp[l][r], left + right)\)
  4. 计算环形答案：

\[ans = \min_{i=0}^{n-1} dp[i][i+n-1] \]

  1. 返回 \(ans\)。

第六步：示例推演

示例：\(target = [1, 2, 1, 2]\)，n=4。

复制一倍：a = [1, 2, 1, 2, 1, 2, 1, 2]。

区间长度 1：dp[i][i]=1。

区间长度 2：
[0,1]: a[0]=1, a[1]=2，先 dp[0][1]=dp[0][0]+1=2。检查 k=0: a[0]!=a[1]，无更新。得 2。
[1,2]: a[1]=2, a[2]=1，同上得 2。
[2,3]: 2
[3,4]: 2
[4,5]: 2
[5,6]: 2
[6,7]: 2

区间长度 3：
[0,2]: a=[1,2,1]
先 dp[0][2]=dp[0][1]+1=3。
k=0: a[0]=1=a[2]，则 left=dp[0][0]=1, right=dp[1][1]=1，sum=2，更小，所以 dp[0][2]=2。
k=1: a[1]!=a[2]，不更新。
结果 2。

先 dp[1][3]=dp[1][2]+1=3。
k=1: a[1]=1!=2，不更新。
k=2: a[2]=2=a[3]，则 left=dp[1][2]=2, right=dp[3][2] 无效(k+1=3>2)，right=0，sum=2，更小，所以 dp[1][3]=2。

类似计算其余。

最后取长度为 4 的区间：
dp[0][3] 计算：
a=[1,2,1,2]
先 dp[0][3]=dp[0][2]+1=3。
k=0: a[0]=1!=2，不更新。
k=1: a[1]=2=a[3]，则 left=dp[0][1]=2, right=dp[2][2]=1，sum=3，不更小。
k=2: a[2]=1!=2，不更新。
所以 dp[0][3]=3。

同样 dp[1][4]=3, dp[2][5]=3, dp[3][6]=3。

环形答案是 min(dp[0][3], dp[1][4], dp[2][5], dp[3][6]) = 3。

总结

这个环形最小涂色问题，本质是“奇怪的打印机”问题的环形版本，通过断环成链 + 区间 DP 解决。关键转移方程是当区间右端与中间某处颜色相同时，可合并染色，减少次数。最终枚举所有长度为 \(n\) 的区间取最小值，得到环形答案。

区间动态规划例题：最小涂色次数问题（分段染色最小成本，相邻段颜色可相同但代价不同，环形版本） 题目描述 你有一个环形序列，由 \( n \) 个连续段组成，每个段可以染成 \( m \) 种颜色之一。染色规则如下： 每次染色必须选择环形序列中的一个 连续子段 （在环上连续），并将其全部染成 同一种颜色 。 已染色的段可以被后面的染色覆盖。 最终目标是要让整个环形序列的第 \( i \) 段颜色为指定目标颜色 \( target[ i ] \)。 每次染色的代价是 1 （无论染多长的子段，代价固定为 1）。 特殊约束：在最终染色结果中， 如果相邻两段颜色相同，它们被视为同一“颜色段” ，并且如果同一颜色段在染色过程中被 分多次染色 ，则每次染色都独立计算代价。但注意，我们最终只关心用最少的总染色次数完成目标颜色序列。 换句话说，我们可以将环形序列按照最终目标颜色分成若干“颜色段”（相邻同色合并），然后问题转化为：用最少染色次数覆盖所有这些颜色段，每次染色覆盖环上一个连续子段，且必须染成同一种颜色（可以和目标颜色不同，但最终必须被覆盖成目标颜色）。求最少染色次数。 输入 ： 整数 \( n \)，环形序列长度。 数组 \( target[ 0..n-1 ] \)，表示每段的目标颜色（用 1~m 表示）。 环形意味着 \( target[ n-1] \) 与 \( target[ 0 ] \) 相邻。 输出 ： 最少染色次数。 示例 ： 环形序列的目标颜色 = [ 1, 2, 1, 2 ]（颜色 1 和 2）。 最少染色次数是 3。 解释： 一种染色方案： 染色整个环为颜色 1。 染色位置 1 和位置 3 为颜色 2（在环上是不连续的两段，所以必须分开两次染色）。 总共 3 次。 解题思路 这是一个 环形区间 DP 问题，关键在于 断环成链 ，并定义状态表示染色一个区间的最少次数。 第一步：简化问题（将环形转化为线性） 环形的难点在于，染色可以跨过环的起点和终点。 常用的方法是：复制一倍数组，然后枚举断点，转化为线性问题求解。 设线性数组长度为 \( 2n \)： \[ \text{newTarget}[ i] = target[ i \bmod n ], \quad i=0..2n-1 \] 我们任取长度为 \( n \) 的一段作为环形展开，但为了处理方便，我们直接考虑在长度为 \( 2n \) 的数组上进行区间 DP，然后取所有长度为 \( n \) 的区间中，从初始全未染色状态到染成目标颜色的最少次数。 但实际上，我们初始状态是全未染色（可视为任意颜色，但未确定），每次染色可覆盖成某种颜色，最终必须匹配目标颜色。 第二步：线性问题的状态定义 设 \( dp[ l][ r] \) 表示将区间 \([ l, r ]\) 染成目标颜色（即最终颜色与 \( target \) 一致）所需的最少染色次数。 注意：区间 \([ l, r ]\) 是线性数组的一段（来自展开后的数组），我们要计算染色它的最少次数。 关键观察： 如果区间内所有目标颜色相同，那么一次染色即可（一次染成这个颜色）。 如果区间两端的目标颜色相同，则最优策略可能是先染一次将该区间染成这个颜色，然后再处理中间不同颜色的部分。但这样可能不是最优，因为先染中间再覆盖两端可能更好。 实际上，这是经典的“奇怪的打印机”问题的扩展，只是颜色数量更多，但每次染色代价固定为 1。 “奇怪的打印机”问题的状态转移： \[ dp[ l][ r ] = \begin{cases} 1 & \text{如果 } l = r \\ \min_ {l \le k < r} (dp[ l][ k] + dp[ k+1][ r ]) & \text{一般情况} \\ dp[ l][ r-1] & \text{如果 } target[ l] = target[ r] \text{ 且 } l < r \end{cases} \] 但最后一条需要更仔细处理：当 \( target[ l] = target[ r] \) 时，我们可以在第一次染色时把 \([ l, r]\) 染成 \( target[ l] \)，然后只需处理中间部分，即 \( dp[ l][ r] = \min(dp[ l][ r], dp[ l][ r-1 ]) \) 吗？ 不完全是。在“奇怪的打印机”中，当两端颜色相同时，最优策略可以是第一次染色时覆盖整个区间为这个颜色，然后内部再调整。此时，第一次染色固定了区间颜色，内部调整只需从 \( l \) 到 \( r-1 \) 的最小次数（因为右端已对，但可能被中间染色覆盖再重新染回来）。 正确转移： \[ dp[ l][ r] = \min(dp[ l][ r-1], dp[ l+1][ r ]) \] 当 \( target[ l] = target[ r] \) 时，因为第一次染色可以染 \([ l, r]\) 为 \( target[ l] \)，之后相当于只处理 \([ l, r-1]\) 或 \([ l+1, r ]\)。 更准确的标准“奇怪的打印机”转移： 基础：\( dp[ l][ r] = 1 + dp[ l][ r-1 ] \) 表示先染 \( r \) 位置，再染左边。 当 \( target[ k] = target[ r] \) 且 \( l \le k < r \) 时，我们可以把区间分成 \([ l, k]\) 和 \([ k+1, r-1]\)，先染 \([ k+1, r]\) 为 \( target[ r ] \)，然后左边再处理。但这样需要仔细推导。 标准方程（来自 LeetCode 奇怪的打印机）： \[ dp[ l][ r] = dp[ l][ r-1 ] + 1 \] 然后尝试 \( k \in [ l, r-1] \)，如果 \( target[ k] = target[ r ] \)，则 \[ dp[ l][ r] = \min(dp[ l][ r], dp[ l][ k] + dp[ k+1][ r-1 ]) \] 这里 \( dp[ k+1][ r-1] \) 表示区间 \([ k+1, r-1 ]\) 的次数，因为第 \( k \) 个位置颜色和 \( r \) 相同，可以在同一次染色覆盖。 第三步：环形处理 将数组复制一倍：\( a[ 0..2n-1] \) 为 \( target[ i \bmod n ] \)。 我们要求的是环形的答案。环形的最小染色次数，等于在 \( 2n \) 数组中选取长度为 \( n \) 的区间的最小染色次数吗？ 不完全是，因为环上染色可以跨过复制点。但我们可以这样处理：在环形中，我们可以固定起点为某个颜色段的首个位置，转化为线性问题。 更简单的方法： 在 \( 2n \) 数组上做区间 DP 后，环形答案 = \[ \min_ {i=0}^{n-1} dp[ i][ i+n-1 ] \] 即任取一段长度为 \( n \) 的区间的最小染色次数。 但要注意：我们的 \( dp[ l][ r ] \) 定义是“从白纸状态（或任意初始状态）染成目标颜色的最少次数”，这里初始状态是未染色，每次染色可任意覆盖，所以这个定义是正确的。 第四步：状态转移方程（最终版） 当 \( l = r \) 时，\( dp[ l][ r ] = 1 \)。 否则： \[ dp[ l][ r] = dp[ l][ r-1 ] + 1 \] 然后遍历 \( k = l \) 到 \( r-1 \)： 如果 \( a[ k] = a[ r ] \)，则 \[ dp[ l][ r] = \min(dp[ l][ r], dp[ l][ k] + dp[ k+1][ r-1 ]) \] 注意：当 \( k = r-1 \) 时，\( dp[ k+1][ r-1] \) 表示空区间，值为 0，所以转移为 \( dp[ l][ r-2] + 1 \) 不对，应直接为 \( dp[ l][ r-1 ] \)。 实际上，空区间处理为 0，所以当 \( k = r-1 \) 时，转移为 \( dp[ l][ r-1 ] + 0 \) 与第一种情况相同，不会更优。 所以这个转移覆盖了“两端颜色相同”时的情况。 第五步：算法步骤 将 \( target \) 数组复制一倍，得到 \( a[ 0..2n-1 ] \)。 初始化 \( dp \) 为 \( 2n \times 2n \) 矩阵，\( dp[ i][ i ] = 1 \)。 按区间长度 \( len = 2 \) 到 \( 2n \)： 遍历起点 \( l \)： \( r = l + len - 1 \)，如果 \( r \ge 2n \) 则跳出。 先令 \( dp[ l][ r] = dp[ l][ r-1 ] + 1 \)。 遍历 \( k = l \) 到 \( r-1 \)： 如果 \( a[ k] = a[ r ] \)： \( left = dp[ l][ k ] \) \( right = 0 \) 如果 \( k+1 > r-1 \)，否则 \( right = dp[ k+1][ r-1 ] \) \( dp[ l][ r] = \min(dp[ l][ r ], left + right) \) 计算环形答案： \[ ans = \min_ {i=0}^{n-1} dp[ i][ i+n-1 ] \] 返回 \( ans \)。 第六步：示例推演 示例：\( target = [ 1, 2, 1, 2 ] \)，n=4。 复制一倍：a = [ 1, 2, 1, 2, 1, 2, 1, 2 ]。 区间长度 1：dp[ i][ i ]=1。 区间长度 2： [ 0,1]: a[ 0]=1, a[ 1]=2，先 dp[ 0][ 1]=dp[ 0][ 0]+1=2。检查 k=0: a[ 0]!=a[ 1 ]，无更新。得 2。 [ 1,2]: a[ 1]=2, a[ 2 ]=1，同上得 2。 [ 2,3 ]: 2 [ 3,4 ]: 2 [ 4,5 ]: 2 [ 5,6 ]: 2 [ 6,7 ]: 2 区间长度 3： [ 0,2]: a=[ 1,2,1 ] 先 dp[ 0][ 2]=dp[ 0][ 1 ]+1=3。 k=0: a[ 0]=1=a[ 2]，则 left=dp[ 0][ 0]=1, right=dp[ 1][ 1]=1，sum=2，更小，所以 dp[ 0][ 2 ]=2。 k=1: a[ 1]!=a[ 2 ]，不更新。 结果 2。 先 dp[ 1][ 3]=dp[ 1][ 2 ]+1=3。 k=1: a[ 1]=1 !=2，不更新。 k=2: a[ 2]=2=a[ 3]，则 left=dp[ 1][ 2]=2, right=dp[ 3][ 2] 无效(k+1=3>2)，right=0，sum=2，更小，所以 dp[ 1][ 3 ]=2。 类似计算其余。 最后取长度为 4 的区间： dp[ 0][ 3 ] 计算： a=[ 1,2,1,2 ] 先 dp[ 0][ 3]=dp[ 0][ 2 ]+1=3。 k=0: a[ 0]=1 !=2，不更新。 k=1: a[ 1]=2=a[ 3]，则 left=dp[ 0][ 1]=2, right=dp[ 2][ 2 ]=1，sum=3，不更小。 k=2: a[ 2]=1 !=2，不更新。 所以 dp[ 0][ 3 ]=3。 同样 dp[ 1][ 4]=3, dp[ 2][ 5]=3, dp[ 3][ 6 ]=3。 环形答案是 min(dp[ 0][ 3], dp[ 1][ 4], dp[ 2][ 5], dp[ 3][ 6 ]) = 3。 总结 这个环形最小涂色问题，本质是“奇怪的打印机”问题的环形版本，通过 断环成链 + 区间 DP 解决。关键转移方程是当区间右端与中间某处颜色相同时，可合并染色，减少次数。最终枚举所有长度为 \( n \) 的区间取最小值，得到环形答案。