合并相邻同色方块的最小成本问题
题目描述：
给定一个颜色数组 colors 和一个成本数组 costs，其中 colors[i] 表示第 i 个方块的颜色，costs[i] 表示移除第 i 个方块的成本。游戏规则是：如果存在三个或更多连续同色方块，可以移除这些方块并获得移除成本的总和。移除后，左右两侧的方块会相邻。请计算通过最优的移除顺序，能够获得的最大总得分。
解题过程：
- 问题分析：
- 这是一个典型的区间动态规划问题
- 我们需要考虑在区间 [i, j] 内，通过最优的移除顺序能获得的最大得分
- 关键点：当移除中间某个区间后，左右两侧可能会连接形成新的连续同色方块
-
状态定义：
定义 dp[i][j] 表示在区间 [i, j] 内通过最优移除顺序能获得的最大得分 -
基础情况：
- 当区间长度小于3时（即 j-i+1 < 3），无法移除任何方块，得分为0
- dp[i][i] = 0，dp[i][i+1] = 0
- 状态转移：
对于区间 [i, j]，考虑以下几种情况：
情况1：直接移除整个区间（如果满足条件）
如果区间 [i, j] 内所有方块颜色相同且长度 ≥ 3，则：
dp[i][j] = sum(costs[i..j])
情况2：分割区间
对于所有可能的分割点 k (i ≤ k < j)：
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])
情况3：移除中间部分后两侧合并
如果 colors[i] == colors[j]，考虑移除中间区间 [l, r] 后，两侧的 i 和 j 相邻：
对于区间 [i, j]，如果存在某个分割方式，移除中间部分后剩下的两端可以继续合并得分
更精确的状态转移：
dp[i][j] = max(
dp[i][j], // 初始值
// 情况1：直接得分（如果满足条件）
(如果区间内所有颜色相同且长度≥3 ? sum(costs[i..j]) : -∞),
// 情况2：分割得分
max_{i≤k<j} (dp[i][k] + dp[k+1][j]),
// 情况3：移除中间后合并得分
... // 这里需要更复杂的处理
)
-
优化状态设计：
为了处理情况3，我们需要更精细的状态定义：
定义 dp[i][j][k] 表示在区间 [i, j] 内，在区间左侧有 k 个与 colors[i] 同色的方块相连时能获得的最大得分 -
完整的状态转移方程：
令 dp[i][j][k] 表示区间 [i, j]，且区间左侧有 k 个与 colors[i] 同色的方块
-
基础情况：当 i > j 时，dp[i][j][k] = 0
-
状态转移：
-
先移除第 i 个方块：dp[i][j][k] = dp[i+1][j][0] + (如果 k ≥ 2 ? costs[i] : 0)
-
不移除第 i 个方块，寻找与 i 同色的位置 m：
for m = i+1 to j:
if colors[i] == colors[m]:
dp[i][j][k] = max(dp[i][j][k],
dp[i+1][m-1][0] + dp[m][j][k+1])
-
-
最终答案：
dp[0][n-1][0]，其中 n 是方块数量 -
实现细节：
- 使用记忆化搜索或自底向上的DP
- 注意边界条件处理
- 时间复杂度：O(n³)，空间复杂度：O(n²)
这个解法通过三维DP状态巧妙地处理了移除中间部分后两侧方块合并的情况，是这类"消消乐"类型问题的经典解法。