区间动态规划例题：合并石子形成目标图案的最小成本（目标图案由多种颜色表示，每次合并相邻石子堆，合并后石子堆的颜色由规则表决定，并有成本）
字数 4397 2025-12-24 23:15:08

区间动态规划例题：合并石子形成目标图案的最小成本（目标图案由多种颜色表示，每次合并相邻石子堆，合并后石子堆的颜色由规则表决定，并有成本）

题目描述

你有一排 n 堆石子，每堆石子有一个初始颜色（用一个字符表示，例如 'R' 表示红色，'G' 表示绿色，'B' 表示蓝色等）。你希望最终通过一系列操作，将所有石子合并成一堆，且这一堆的颜色必须与一个给定的目标图案（也是一个字符）相同。

操作规则如下：

  1. 你每次只能合并相邻的两堆石子。

  2. 当你合并两堆相邻的石子时，合并后的新堆的颜色由一个给定的颜色合并规则表决定。这个表可以看作一个映射：(color_left, color_right) -> (new_color, merge_cost)。其中：

    • color_left 和 color_right 分别表示被合并的两堆石子的颜色。
    • new_color 是合并后新石子堆的颜色。
    • merge_cost 是本次合并操作的成本（是一个非负整数）。

  3. 你的目标是计算将所有石子合并成一堆，并且这堆的颜色是目标颜色 target 所需的最小总成本。如果无法通过任何合并序列得到目标颜色，则返回 -1。

示例
假设石子初始颜色数组为：colors = ['R', 'G', 'B']，目标颜色为 target = 'Y'。
颜色合并规则表如下（这里只是示意，实际题目会给出具体表）：

  • 合并 ('R', 'G') -> ('B', 3)
  • 合并 ('G', 'B') -> ('R', 2)
  • 合并 ('R', 'B') -> ('G', 4)
  • 合并 ('G', 'R') -> ('B', 3) （注意：顺序可能重要，即 (左,右) 与 (右,左) 可能不同）
  • 等等... 如果规则表中没有给出某种颜色对的合并方式，意味着这两堆不能直接合并。

我们需要找出一种合并顺序，使得最后剩下的一堆颜色为 'Y'，并且总合并成本最小。

解题思路（动态规划）

这个问题本质上是一个区间DP，因为涉及对一段连续的石子堆进行合并，最终得到一个结果（颜色和成本）。
我们可以定义状态来表示一段区间合并后的可能结果，然后逐步合并，最终得到整个区间合并为目标颜色的最小成本。

1. 状态定义

设石子堆下标从 0 到 n-1。
定义 dp[i][j][c] 表示将下标从 i 到 j（闭区间）的石子堆合并成颜色为 c 的一堆所需的最小成本。
如果无法合并成颜色 c，则 dp[i][j][c] = INF（一个很大的数，表示不可能）。

这里 c 的取值范围是所有可能的颜色集合（包括初始颜色和合并后可能产生的颜色，题目通常会给出所有可能出现的颜色）。

2. 状态转移

考虑区间 [i, j] 如何合并成一堆颜色 c：

  • 如果 i == j，即区间只有一堆石子。那么只有一种可能：这堆石子的初始颜色就是 c，则成本为 0；否则不可能，成本为 INF。

  • 如果 i < j，我们需要选择一个分割点 k（i <= k < j），将区间分成两部分：[i, k] 和 [k+1, j]。
    分别将左半部分合并成某种颜色 a，右半部分合并成某种颜色 b，然后根据规则表，将颜色为 a 和 b 的两堆合并成颜色 c。
    因此转移方程为：

    dp[i][j][c] = min(dp[i][j][c], dp[i][k][a] + dp[k+1][j][b] + cost(a, b, c))

    其中 cost(a, b, c) 表示将颜色 a 和 b 的两堆合并成颜色 c 所需的成本（如果规则允许的话），如果规则不允许（即规则表中没有对应条目），则为 INF。

    我们需要枚举所有可能的分割点 k 和所有可能的中间颜色 a 和 b，然后检查规则表是否支持 (a, b) -> (c, cost)。

3. 初始化和边界

  • 初始化 dp[i][i][color_i] = 0，其中 color_i 是第 i 堆的初始颜色。
    对于其他颜色，dp[i][i][c] = INF。
  • 对于 i > j 的情况不考虑（无效区间）。
  • 对于长度 len 从 2 到 n 逐步计算。

4. 答案

答案是 dp[0][n-1][target]，如果它等于 INF，则说明无法合并成目标颜色，返回 -1。

逐步详解（以一个简单例子为例）

假设：

  • 初始石子堆：colors = ['R', 'G', 'B']
  • 目标颜色：target = 'Y'
  • 可能的颜色集合：{R, G, B, Y, W} （W 是另一种可能颜色，但这里用不到）
  • 合并规则表（只列出部分，实际可能更多）：
规则1: (R, G) -> (B, 3)
规则2: (G, B) -> (R, 2)
规则3: (R, B) -> (Y, 5)
规则4: (B, R) -> (Y, 4)  // 注意顺序可能不同
规则5: (Y, R) -> (Y, 1)
规则6: (Y, G) -> (Y, 2)

步骤1：初始化
区间长度=1（单堆）
dp[0][0]['R'] = 0
dp[1][1]['G'] = 0
dp[2][2]['B'] = 0
其他颜色均为 INF。

步骤2：区间长度=2

区间 [0,1]（颜色 R 和 G）
合并方式：

  • 尝试规则1: (R,G)->(B,3)
    所以 dp[0][1]['B'] = dp[0][0]['R'] + dp[1][1]['G'] + 3 = 0+0+3 = 3
  • 无其他规则匹配 (R,G)，所以 dp[0][1] 的其他颜色为 INF。

区间 [1,2]（颜色 G 和 B）

  • 规则2: (G,B)->(R,2)
    dp[1][2]['R'] = dp[1][1]['G'] + dp[2][2]['B'] + 2 = 0+0+2 = 2

步骤3：区间长度=3

区间 [0,2]（即整个数组 R,G,B）
我们枚举分割点 k：

k=0：左边 [0,0] (R)，右边 [1,2] (已合并为某种颜色)

  • 右边可能颜色：已知 dp[1][2]['R']=2
  • 检查 (R, R) 合并规则，但规则表无，跳过。
  • 如果右边是其他颜色，但 dp[1][2] 只有 'R' 可行，所以只有 (R,R) 组合，但不可合并，所以无更新。

k=1：左边 [0,1] (已合并为某种颜色)，右边 [2,2] (B)
左边可能颜色：dp[0][1]['B']=3

  • 合并 (B, B)：规则表无，跳过。
  • 左边也可能有其他颜色，但这里只有 'B' 可行。

所以目前还无法得到目标颜色 Y。

我们需要检查其他合并顺序：实际上，对于区间 [0,2]，我们可以先合并后两个，再与第一个合并，或者先合并前两个，再与最后一个合并。但这里规则表没有直接支持 (R,G,B) 一步到 Y，需要分两步。

重新审视规则表：
规则3: (R, B) -> (Y, 5)
规则4: (B, R) -> (Y, 4)

如果我们能先得到 (R,B) 或 (B,R) 就可以直接得到 Y。

考虑 k=0 时，左边是 R，右边是 (G,B) 合并为 R（成本2），但 (R,R) 不能合并为 Y。
考虑 k=1 时，左边是 (R,G) 合并为 B（成本3），右边是 B，但 (B,B) 不能合并为 Y。

所以从初始状态似乎无法直接得到 Y？
等等，我们需要检查所有可能的中间颜色组合。
实际上，我们可以让 [0,1] 合并为 B（成本3），然后 [1,2] 合并为 R（成本2） 吗？不，[1,2] 是一个整体，我们不能同时用 [1,2] 做两种合并。

正确做法：
对于区间 [0,2]，我们枚举左边颜色 a 和右边颜色 b，然后检查规则表是否能合并为 c=Y。

首先计算 dp[0][1] 和 dp[2][2] 的组合：
dp[0][1] 只有颜色 B（成本3），dp[2][2] 只有颜色 B（成本0）
(B,B) 没有规则合并为 Y。

然后计算 dp[0][0] 和 dp[1][2] 的组合：
dp[0][0] 只有 R（0），dp[1][2] 只有 R（2）
(R,R) 没有规则合并为 Y。

所以看起来无法得到 Y？
但我们可能漏了一种情况：区间 [0,2] 可以分割成 [0,0] 和 [1,2] 但右边是 G 和 B 合并为 R，但 (R,R) 不行。
也可以分割成 [0,1] 和 [2,2]，左边是 B，右边是 B，不行。

所以根据给定规则，确实无法得到 Y。但如果我们增加一条规则 (B, R) -> (Y,4)，那么：

先合并后两个 (G,B) 为 R（成本2），此时剩下 R 和 R，但 (R,R) 不行。
先合并前两个 (R,G) 为 B（成本3），剩下 B 和 B，不行。
所以还是不行。

实际上，要得到 Y，需要 (R,B) 或 (B,R)。
初始是 R,G,B。
如果我们先合并 (G,B) 为 R（成本2），得到 R,R，不行。
如果我们先合并 (R,G) 为 B（成本3），得到 B,B，不行。
所以确实无法得到 Y。

但如果规则表增加 (B, B) -> (Y,1)，那么：
先合并 (R,G) 为 B（成本3），得到 B,B，再合并为 Y（成本1），总成本 4。
这样 dp[0][2]['Y'] = 4。

算法实现要点

  1. 将所有颜色映射到整数索引，方便数组存储。
  2. 用一个三维数组 cost[a][b][c] 存储规则：将颜色 a 和 b 合并为 c 的成本（若无对应规则，则设为 INF）。
  3. 状态转移时，枚举分割点 k，然后枚举左区间可能的颜色 a 和右区间可能的颜色 b，再枚举目标颜色 c，如果 cost[a][b][c] 不是 INF，则更新 dp[i][j][c]。
  4. 最终答案是 dp[0][n-1][target_color_index]。

复杂度分析

  • 状态数：O(n² * C)，其中 C 是颜色数量。
  • 转移：枚举分割点 O(n)，枚举左颜色 O(C)，右颜色 O(C)，目标颜色 O(C)，所以每个状态转移是 O(n * C³)。
  • 总复杂度：O(n³ * C³)，在 n 较小（如 ≤ 50）和 C 较小（如 ≤ 5）时可接受。

总结

这道题是区间DP的典型应用，与“石子合并”类似，但增加了“颜色合并规则”和“目标颜色”的限制。
核心在于定义状态 dp[i][j][c] 表示区间合并成颜色 c 的最小成本，然后通过枚举分割点和中间颜色进行合并。
如果最终 dp[0][n-1][target] 为 INF，则表示无法得到目标颜色。

区间动态规划例题：合并石子形成目标图案的最小成本（目标图案由多种颜色表示，每次合并相邻石子堆，合并后石子堆的颜色由规则表决定，并有成本） 题目描述 你有一排 n 堆石子，每堆石子有一个初始颜色（用一个字符表示，例如 'R' 表示红色，'G' 表示绿色，'B' 表示蓝色等）。你希望最终通过一系列操作，将所有石子合并成一堆，且这一堆的颜色必须与一个 给定的目标图案 （也是一个字符）相同。 操作规则如下： 你每次只能合并 相邻的两堆石子 。 当你合并两堆相邻的石子时，合并后的新堆的颜色由一个给定的 颜色合并规则表 决定。这个表可以看作一个映射： (color_left, color_right) -> (new_color, merge_cost) 。其中： color_left 和 color_right 分别表示被合并的两堆石子的颜色。 new_color 是合并后新石子堆的颜色。 merge_cost 是本次合并操作的成本（是一个非负整数）。 你的目标是计算将所有石子合并成 一堆 ，并且这堆的颜色是 目标颜色 target 所需的最小总成本。如果无法通过任何合并序列得到目标颜色，则返回 -1。 示例 假设石子初始颜色数组为： colors = ['R', 'G', 'B'] ，目标颜色为 target = 'Y' 。 颜色合并规则表如下（这里只是示意，实际题目会给出具体表）： 合并 ('R', 'G') -> ('B', 3) 合并 ('G', 'B') -> ('R', 2) 合并 ('R', 'B') -> ('G', 4) 合并 ('G', 'R') -> ('B', 3) （注意：顺序可能重要，即 (左,右) 与 (右,左) 可能不同） 等等... 如果规则表中没有给出某种颜色对的合并方式，意味着这两堆不能直接合并。 我们需要找出一种合并顺序，使得最后剩下的一堆颜色为 'Y'，并且总合并成本最小。 解题思路（动态规划） 这个问题本质上是一个 区间DP ，因为涉及对一段连续的石子堆进行合并，最终得到一个结果（颜色和成本）。 我们可以定义状态来表示一段区间合并后的可能结果，然后逐步合并，最终得到整个区间合并为目标颜色的最小成本。 1. 状态定义 设石子堆下标从 0 到 n-1。 定义 dp[i][j][c] 表示将下标从 i 到 j （闭区间）的石子堆合并成 颜色为 c 的一堆 所需的最小成本。 如果无法合并成颜色 c，则 dp[i][j][c] = INF （一个很大的数，表示不可能）。 这里 c 的取值范围是所有可能的颜色集合（包括初始颜色和合并后可能产生的颜色，题目通常会给出所有可能出现的颜色）。 2. 状态转移 考虑区间 [i, j] 如何合并成一堆颜色 c： 如果 i == j ，即区间只有一堆石子。那么只有一种可能：这堆石子的初始颜色就是 c，则成本为 0；否则不可能，成本为 INF。 如果 i < j ，我们需要选择一个分割点 k （ i <= k < j ），将区间分成两部分： [i, k] 和 [k+1, j] 。 分别将左半部分合并成某种颜色 a ，右半部分合并成某种颜色 b ，然后根据规则表，将颜色为 a 和 b 的两堆合并成颜色 c 。 因此转移方程为： dp[i][j][c] = min(dp[i][j][c], dp[i][k][a] + dp[k+1][j][b] + cost(a, b, c)) 其中 cost(a, b, c) 表示将颜色 a 和 b 的两堆合并成颜色 c 所需的成本（如果规则允许的话），如果规则不允许（即规则表中没有对应条目），则为 INF。 我们需要枚举所有可能的分割点 k 和所有可能的中间颜色 a 和 b ，然后检查规则表是否支持 (a, b) -> (c, cost) 。 3. 初始化和边界 初始化 dp[i][i][color_i] = 0 ，其中 color_i 是第 i 堆的初始颜色。 对于其他颜色， dp[i][i][c] = INF 。 对于 i > j 的情况不考虑（无效区间）。 对于长度 len 从 2 到 n 逐步计算。 4. 答案 答案是 dp[0][n-1][target] ，如果它等于 INF，则说明无法合并成目标颜色，返回 -1。 逐步详解（以一个简单例子为例） 假设： 初始石子堆： colors = ['R', 'G', 'B'] 目标颜色： target = 'Y' 可能的颜色集合：{R, G, B, Y, W} （W 是另一种可能颜色，但这里用不到） 合并规则表（只列出部分，实际可能更多）： 步骤1：初始化 区间长度=1（单堆） dp[ 0][ 0][ 'R' ] = 0 dp[ 1][ 1][ 'G' ] = 0 dp[ 2][ 2][ 'B' ] = 0 其他颜色均为 INF。 步骤2：区间长度=2 区间 [ 0,1 ]（颜色 R 和 G） 合并方式： 尝试规则1: (R,G)->(B,3) 所以 dp[ 0][ 1][ 'B'] = dp[ 0][ 0][ 'R'] + dp[ 1][ 1][ 'G' ] + 3 = 0+0+3 = 3 无其他规则匹配 (R,G)，所以 dp[ 0][ 1 ] 的其他颜色为 INF。 区间 [ 1,2 ]（颜色 G 和 B） 规则2: (G,B)->(R,2) dp[ 1][ 2][ 'R'] = dp[ 1][ 1][ 'G'] + dp[ 2][ 2][ 'B' ] + 2 = 0+0+2 = 2 步骤3：区间长度=3 区间 [ 0,2 ]（即整个数组 R,G,B） 我们枚举分割点 k： k=0：左边 [ 0,0] (R)，右边 [ 1,2 ] (已合并为某种颜色) 右边可能颜色：已知 dp[ 1][ 2][ 'R' ]=2 检查 (R, R) 合并规则，但规则表无，跳过。 如果右边是其他颜色，但 dp[ 1][ 2 ] 只有 'R' 可行，所以只有 (R,R) 组合，但不可合并，所以无更新。 k=1：左边 [ 0,1] (已合并为某种颜色)，右边 [ 2,2 ] (B) 左边可能颜色：dp[ 0][ 1][ 'B' ]=3 合并 (B, B)：规则表无，跳过。 左边也可能有其他颜色，但这里只有 'B' 可行。 所以目前还无法得到目标颜色 Y。 我们需要检查其他合并顺序：实际上，对于区间 [ 0,2 ]，我们可以先合并后两个，再与第一个合并，或者先合并前两个，再与最后一个合并。但这里规则表没有直接支持 (R,G,B) 一步到 Y，需要分两步。 重新审视规则表： 规则3: (R, B) -> (Y, 5) 规则4: (B, R) -> (Y, 4) 如果我们能先得到 (R,B) 或 (B,R) 就可以直接得到 Y。 考虑 k=0 时，左边是 R，右边是 (G,B) 合并为 R（成本2），但 (R,R) 不能合并为 Y。 考虑 k=1 时，左边是 (R,G) 合并为 B（成本3），右边是 B，但 (B,B) 不能合并为 Y。 所以从初始状态似乎无法直接得到 Y？ 等等，我们需要检查所有可能的中间颜色组合。 实际上，我们可以让 [ 0,1] 合并为 B（成本3），然后 [ 1,2] 合并为 R（成本2） 吗？不，[ 1,2] 是一个整体，我们不能同时用 [ 1,2 ] 做两种合并。 正确做法 ： 对于区间 [ 0,2 ]，我们枚举左边颜色 a 和右边颜色 b，然后检查规则表是否能合并为 c=Y。 首先计算 dp[ 0][ 1] 和 dp[ 2][ 2 ] 的组合： dp[ 0][ 1] 只有颜色 B（成本3），dp[ 2][ 2 ] 只有颜色 B（成本0） (B,B) 没有规则合并为 Y。 然后计算 dp[ 0][ 0] 和 dp[ 1][ 2 ] 的组合： dp[ 0][ 0] 只有 R（0），dp[ 1][ 2 ] 只有 R（2） (R,R) 没有规则合并为 Y。 所以看起来无法得到 Y？ 但我们可能漏了一种情况：区间 [ 0,2] 可以分割成 [ 0,0] 和 [ 1,2 ] 但右边是 G 和 B 合并为 R，但 (R,R) 不行。 也可以分割成 [ 0,1] 和 [ 2,2 ]，左边是 B，右边是 B，不行。 所以根据给定规则，确实无法得到 Y。但如果我们增加一条规则 (B, R) -> (Y,4)，那么： 先合并后两个 (G,B) 为 R（成本2），此时剩下 R 和 R，但 (R,R) 不行。 先合并前两个 (R,G) 为 B（成本3），剩下 B 和 B，不行。 所以还是不行。 实际上，要得到 Y，需要 (R,B) 或 (B,R)。 初始是 R,G,B。 如果我们先合并 (G,B) 为 R（成本2），得到 R,R，不行。 如果我们先合并 (R,G) 为 B（成本3），得到 B,B，不行。 所以确实无法得到 Y。 但如果规则表增加 (B, B) -> (Y,1)，那么： 先合并 (R,G) 为 B（成本3），得到 B,B，再合并为 Y（成本1），总成本 4。 这样 dp[ 0][ 2][ 'Y' ] = 4。 算法实现要点 将所有颜色映射到整数索引，方便数组存储。 用一个三维数组 cost[ a][ b][ c ] 存储规则：将颜色 a 和 b 合并为 c 的成本（若无对应规则，则设为 INF）。 状态转移时，枚举分割点 k，然后枚举左区间可能的颜色 a 和右区间可能的颜色 b，再枚举目标颜色 c，如果 cost[ a][ b][ c] 不是 INF，则更新 dp[ i][ j][ c ]。 最终答案是 dp[ 0][ n-1][ target_ color_ index ]。 复杂度分析 状态数：O(n² * C)，其中 C 是颜色数量。 转移：枚举分割点 O(n)，枚举左颜色 O(C)，右颜色 O(C)，目标颜色 O(C)，所以每个状态转移是 O(n * C³)。 总复杂度：O(n³ * C³)，在 n 较小（如 ≤ 50）和 C 较小（如 ≤ 5）时可接受。 总结 这道题是区间DP的典型应用，与“石子合并”类似，但增加了“颜色合并规则”和“目标颜色”的限制。 核心在于定义状态 dp[ i][ j][ c ] 表示区间合并成颜色 c 的最小成本，然后通过枚举分割点和中间颜色进行合并。 如果最终 dp[ 0][ n-1][ target ] 为 INF，则表示无法得到目标颜色。