合并相邻同色方块的最小成本问题（相邻染色限制版本）

题目描述
给定一个长度为 n 的字符串 s，每个字符表示一个方块的颜色。你每次可以选择两个相邻的同色方块进行合并，合并后的新方块颜色可以任意选择（但需满足题目给定的染色限制：新方块的颜色必须与原来两个方块的颜色之一相同）。合并的成本为两个方块的颜色值之和（假设颜色已映射为整数，例如 'a'→1, 'b'→2 等）。目标是合并所有方块为一个方块，求最小总成本。

解题过程

1. 问题分析
   本题是区间动态规划的典型应用。我们需要将整个字符串逐步合并为一个方块，每次合并相邻的同色方块，且合并后的颜色只能是原两个颜色之一。关键在于定义状态和状态转移方程，以覆盖所有可能的合并顺序和颜色选择。

2. 状态定义
   设 dp[i][j][c] 表示将子串 s[i:j+1] 合并为一个颜色为 c 的方块所需的最小成本。其中 c 是颜色的整数映射（例如 'a'→0, 'b'→1 等）。由于颜色数量有限，我们可以用 0 到 k-1 表示 k 种颜色。

3. 初始化
   对于长度为 1 的区间 [i, i]，如果该方块的颜色为 c，则 dp[i][i][c] = 0（无需合并），否则 dp[i][i][c] = ∞（不可行）。

4. 状态转移
   对于区间 [i, j]（长度 len > 1），我们枚举分割点 k（i ≤ k < j），将区间分为 [i, k] 和 [k+1, j] 两部分。假设左部分合并后颜色为 c1，右部分合并后颜色为 c2，且 c1 和 c2 需满足合并条件（c1 == c2 时才能合并）。合并后的颜色必须是 c1 或 c2，成本为 cost = c1_value + c2_value（颜色值之和）。
   状态转移方程为：

   dp[i][j][c] = min(dp[i][j][c], dp[i][k][c1] + dp[k+1][j][c2] + cost)
   

   其中 c 取 c1 或 c2。

5. 最终答案
   所有方块合并后，颜色可以是任意一种，因此答案为 min(dp[0][n-1][c])，c 遍历所有颜色。

6. 复杂度优化
   直接三维 DP 的复杂度为 O(n³ × k²)，可能较高。若颜色数 k 较小（如 k ≤ 26），则可行。若 k 较大，可考虑预处理同色块合并的优化，或使用状态压缩（如只记录可行颜色）。

示例
假设 s = "aba"，颜色映射 a→1, b→2。

• 初始：dp[0][0][a]=0, dp[1][1][b]=0, dp[2][2][a]=0，其余 ∞。
• 合并 [0,1]：颜色需相同，但 a≠b，不可行。
• 合并 [1,2]：b≠a，不可行。
• 合并 [0,2]：通过中间分割点 k=1，先合并 [0,1] 和 [2,2] 或 [0,0] 和 [1,2]，但需保证左右颜色相同。最终通过多次分割尝试，找到最小成本路径。

通过以上步骤，可系统求解最小合并成本。