dp[i][i][c] = (c == colors[i]) ? 0 : gain[1][c];

合并相邻同色方块的最小成本问题（颜色扩展与合并收益） 1. 问题描述 有一个长度为 n 的数组 colors ，表示一排方块的颜色（颜色用整数表示）。 每次操作可以合并 相邻且颜色相同 的连续一段方块，合并后这段方块会变成一个 新方块 ，其颜色可以变为另一种颜色（也可以不变），合并的 收益 取决于合并的长度和新颜色，收益可能为正也可能为负。 你的目标是经过若干次合并操作，最终只剩下一个方块，使得 总收益最大 。 更形式化的定义 ： 初始数组 colors[0..n-1] 。 合并区间 [i, j] 的条件是：区间内所有方块颜色相同（即 colors[i] = colors[i+1] = ... = colors[j] ）。 合并区间 [i, j] 后，这个区间变成一个方块，颜色可以变成任意一个整数（包括原来的颜色），收益为 gain[length][newColor] ，其中 length = j-i+1 ， gain 是一个给定的二维表，表示将长度为 length 的某颜色区间合并成颜色 newColor 的收益（可能为负）。 合并后，左右两边的方块会相邻，可以继续合并。 问：从初始数组开始，经过任意次合并，最终只剩一个方块时，能获得的最大总收益。 2. 示例 设颜色只有 0 和 1，初始数组： [0, 0, 1, 1] 。 gain 表（简化示例，长度最大 4，颜色 0/1）： 长度 = 2 时： 合并成颜色 0，收益 5； 合并成颜色 1，收益 3。 长度 = 3 时： 合并成颜色 0，收益 8； 合并成颜色 1，收益 6。 长度 = 4 时： 合并成颜色 0，收益 12； 合并成颜色 1，收益 10。 初始数组无法一次性合并整个数组，因为中间颜色不同。 一种合并顺序： 合并前两个 0（长度 2，颜色相同 0，合并成颜色 0，收益 5），数组变为 [0, 1, 1] 。 合并后两个 1（长度 2，颜色相同 1，合并成颜色 1，收益 3），数组变为 [0, 1] 。 此时 [0, 1] 颜色不同，不能直接合并，需先让某个区间合并改变颜色，但这里长度 2 颜色不同，无法合并，所以这个顺序不行。 正确思路：先分别合并相邻同色的，让区间变短，再通过合并得到相同颜色，最后合并整体。 本题需要用 区间动态规划 记录每个区间合并成某种颜色的最大收益。 3. 区间 DP 状态定义 设 dp[i][j][c] = 将区间 [i, j] 合并成 颜色 c 时，能获得的最大收益。 如果区间 [i, j] 不能合并成颜色 c，则值为负无穷。 初始时，长度 1 的区间： dp[i][i][colors[i]] = 0 （不合并，收益 0）。 dp[i][i][c] （c ≠ colors[ i]） = 不可能，因为单个方块颜色固定，不能变成其他颜色，除非合并长度=1 时允许变化？题目说合并后可以变成任意颜色，但合并操作的输入是 一段颜色相同的区间 ，单个方块本身是颜色相同的区间（长度 1），所以可以一次操作把它变成其他颜色，收益是 gain[1][c] 。 所以对长度 1 的区间， dp[i][i][c] = gain[1][c] 吗？ 不，因为一开始的单个方块已经是颜色 colors[i] ，要变成颜色 c 需要一次“合并”操作（长度 1 的合并），收益 = gain[1][c] 。 但这是“一次操作”之后的收益，初始数组的方块并未经过操作，所以它的收益是 0 当颜色是原色。 我们约定： dp[i][j][c] 表示经过若干操作，最终区间 [i, j] 变成 一个颜色为 c 的方块 ，获得的最大总收益。 那么对于 i==j ： 如果 c == colors[ i ]，则不需要操作，收益 0。 如果 c != colors[ i]，则需要一次合并操作（区间长度 1 合并成颜色 c），收益 = gain[1][c] 。 但注意：合并操作要求区间内颜色相同，长度 1 显然颜色相同，所以允许。 因此初始化： 但这里有个问题： gain[1][c] 可能为负数，如果为负，我们不一定要做这个操作，但题目要求最终颜色 c，就必须做，所以即使负也要接受（因为最后要变成颜色 c）。 如果题目允许最终颜色任选，我们会在最后取最大值，所以这里初始值必须准确。 4. 状态转移 考虑区间 [i, j] 如何变成颜色 c。 有两种情况： 最后一次合并是整个区间 [i, j] 直接合并成颜色 c。 条件：区间 [i, j] 在合并之前必须颜色相同（设为 c0），然后一次合并，收益 = gain[len][c] ，其中 len = j-i+1。 那么合并之前的收益是： dp[i][j][c0] 吗？不， dp[i][j][c0] 已经表示区间 [i,j] 变成颜色 c0 的最大收益，而颜色 c0 必须和初始区间内颜色一致？ 更准确：最后一次合并前， [i, j] 是颜色相同的某个颜色 c0，然后一次合并变成 c，总收益 = dp[i][j][c0] + gain[len][c] ，但 dp[i][j][c0] 怎么得到？ 其实更自然的想法是：我们枚举最后一步合并的划分。 更通用的区间 DP 思路： 对区间 [i, j] ，枚举最后一次合并的区间 [k, t] ？这不太合适，因为最后一次合并可能涉及多个子区间合并后的结果。 实际上这类“合并相邻同色区间”问题，常用方法是： 先枚举区间内第一个块最终和哪些块一起合并。 但更直接的方法是： 将区间 [i, j] 分成两部分 [i, m] 和 [m+1, j] ，让这两部分分别合并成相同颜色 c0，然后再合并这两个颜色为 c0 的块（因为相邻且颜色相同），变成颜色 c，收益是 gain[2][c] 。 但这样要求两部分颜色都是 c0，然后合并时长度为 2，收益为 gain[2][c] 。 但这里有个问题：原始数组的两部分颜色可能不同，但经过之前操作，它们都能变成 c0，所以可以。 但这样只覆盖了最后一步是长度为 2 的合并，不全面。 更合理的状态转移 ： 考虑区间 [i, j] 如何得到颜色 c。 我们可以先让区间内某个连续子段合并成相同颜色 c0，然后再合并整个区间（因为整个区间颜色相同 c0），变成颜色 c，收益是 gain[len][c] 。 所以关键是如何让整个区间变成相同颜色 c0。 让整个区间变成相同颜色 c0 的方法： 如果区间长度 1，上面已初始化。 如果长度 >1，可以先把区间分成 [i, k] 和 [k+1, j] ，让它们都变成颜色 c0，那么整个区间颜色就是 c0，不需要额外操作（因为相邻两个块颜色相同，但它们已经是一个块了吗？不，它们还是两个块，要合并成一个块，需要一次操作，收益是 gain[2][c0] 吗？不，这个操作合并两个块，长度为 2，收益是 gain[2][c] 如果我们想变成 c 的话）。 这有点绕，我们换一种更清晰的定义。 5. 重新定义状态（更清晰） 设 same[i][j] 表示将区间 [i, j] 变成 所有方块颜色相同 （任意颜色）所需的最大收益，不要求变成一个方块。 但题目要求最终一个方块，所以必须合并成一个方块。 所以我们定义： f[i][j] = 将区间 [i, j] 合并成 一个方块 （任意颜色）的最大收益。 最终答案 = f[0][n-1] 。 怎么转移？ 考虑最后一步合并： 我们将 [i, j] 分成 [i, k] 和 [k+1, j] ，分别合并成一个方块，颜色可以不同，但合并最后一步要求两个方块颜色相同，所以需要让其中一块变色（通过一次长度为 1 的合并操作），或者让它们在之前就变成相同颜色。 这样会很复杂，因为颜色处理麻烦。 6. 标准解法状态设计 这是经典的“合并相邻同色”问题变种，用三维 DP： dp[i][j][c] 表示区间 [i, j] 合并成一个颜色为 c 的方块的最大收益。 初始化： dp[i][i][c] = (c == colors[i]) ? 0 : gain[1][c] 。 转移： 如果区间 [i, j] 最后一步是直接由整个区间（颜色相同）合并成颜色 c，则： 先让区间 [i, j] 变成某种颜色 c0（整个区间颜色相同），收益是 same[i][j][c0] 吗？不， same[i][j][c0] 就等价于 dp[i][j][c0] 吗？不对， dp[i][j][c0] 已经是一个方块，所以整个区间颜色相同且是一个方块。 所以这个情况已包含在 dp 中，不需要单独转移。 枚举分界点 k，将区间分成 [i, k] 和 [k+1, j] ，分别合并成颜色 c1 和 c2。 如果 c1 == c2，则可以将这两个方块合并，合并长度 = 2，收益是 gain[2][c] ，c 是合并后的颜色。 所以： dp[i][j][c] = max(dp[i][k][c1] + dp[k+1][j][c1] + gain[2][c]) 对所有 c1, k 和 c。 如果 c1 != c2，则无法直接合并，需要将其中一个方块先和别的合并，但这里分界可能不完整。 所以更通用的方法是： 先枚举最后一步合并的区间 [p, q] （它是区间内一个连续段，且颜色相同），但这样复杂。 实际上这类题的标准简化： 我们只考虑最后一步合并的是相邻两个同色块，而这两个块可能是由更小区间合并来的。 所以转移： dp[i][j][c] = max( dp[i][k][c] + dp[k+1][j][c] + gain[2][c] ) 对所有 k。 但这样要求左右两半合并成相同颜色 c，然后合并这两个块（长度 2）成颜色 c。 但这样收益是 gain[2][c] ，实际上最后一步合并的长度是 2，但整个区间长度 >2，显然不对，因为最后一步合并的长度应该是整个区间的长度。 7. 正确转移 我们意识到，合并操作的长度是当前合并的区间长度。 所以最后一步合并的长度是 j-i+1。 那么条件是在合并前，整个区间 [i, j] 必须颜色相同（某个颜色 c0）。 所以我们先要得到 dp[i][j][c0] ，然后最后一步收益是 gain[len][c] 。 那么怎么得到 dp[i][j][c0] ？ 我们可以枚举第一个块的位置： 区间 [i, j] 先让 [i, m] 合并成颜色 c0，让 [m+1, j] 也变成颜色 c0，但这两部分可能内部还需要合并，并且最终是两个块，颜色都是 c0，然后合并这两个块（长度为 2），得到颜色 c0，但这样长度是 2，不是 len。 这显示出矛盾：我们想最后一步合并长度是 len，但转移时合并的是两个块，长度只能是 2。 除非我们把最后一步看成是合并多个连续的颜色 c0 的块，但那些块本身可能由多个原始块合并来。 实际上，正确做法是： 设 g[i][j] 表示区间 [i, j] 合并成一个方块（任意颜色）的最大收益。 转移时，枚举最后一步合并的区间 [i, k] 和 [k+1, j] ，但这样需要它们颜色相同，设颜色为 c，则： g[i][j] = max( g[i][k] + g[k+1][j] + gain[2][c] ) 对所有 k, c 且 dp[i][k][c] , dp[k+1][j][c] 有意义。 但这样需要先知道 dp[i][k][c] 的值。 所以要先计算 dp[i][j][c] 。 计算 dp[i][j][c] ： 要么整个区间一步合并成 c：需要初始整个区间颜色相同 c0，收益 = gain[len][c] ，但初始整个区间颜色相同吗？不一定，所以不能直接。 所以只能从更小的区间组合来。 8. 最终采用的可行方法 我们这样转移： 如果区间 [i, j] 可以合并成一个颜色 c 的方块，那么最后一步一定是以某个颜色 c0 合并整个区间，然后变成 c。 所以 dp[i][j][c] = max( same[i][j][c0] + gain[len][c] ) ，其中 same[i][j][c0] 表示将区间 [i, j] 合并成一个颜色为 c0 的方块的最大收益。 而 same[i][j][c0] 就是 dp[i][j][c0] 。 所以 dp[i][j][c] = max( dp[i][j][c0] + gain[len][c] ) 对所有 c0。 如何计算 dp[i][j][c0] ？ 它可以由两个相邻子区间合并成相同颜色 c0 得到： dp[i][j][c0] = max( dp[i][k][c0] + dp[k+1][j][c0] + gain[2][c0] ) 对所有 k。 这样我们就有了两个转移方程： (1) dp[i][j][c] = max{ dp[i][j][c0] + gain[len][c] } 对所有 c0。 (2) dp[i][j][c0] = max{ dp[i][k][c0] + dp[k+1][j][c0] + gain[2][c0] } 对所有 k。 初始条件： dp[i][i][c] = (c == colors[i]) ? 0 : gain[1][c] 。 然后按长度从小到大计算即可。 9. 算法步骤 读入 colors[ 0..n-1] 和 gain[ 1..n][ 0..C-1 ]（C 是颜色总数）。 初始化 dp 为 -inf。 对于每个 i，对每种颜色 c： 如果 c == colors[ i]，dp[ i][ i][ c ] = 0。 否则 dp[ i][ i][ c] = gain[ 1][ c ]。 对于长度 len 从 2 到 n： 对于每个起点 i（j = i+len-1）： 对每种颜色 c0： 对每个 k 从 i 到 j-1： dp[ i][ j][ c0] = max(dp[ i][ j][ c0], dp[ i][ k][ c0] + dp[ k+1][ j][ c0] + gain[ 2][ c0 ])。 对每种颜色 c： 对每种颜色 c0： dp[ i][ j][ c] = max(dp[ i][ j][ c], dp[ i][ j][ c0] + gain[ len][ c ])。 最终答案 = max{ dp[ 0][ n-1][ c ] } 对所有颜色 c。 时间复杂度 O(n^3 * C^2)，可优化为 O(n^3 * C)。 10. 举例验证（简例） n=2, colors=[ 0,0 ], C=2。 gain[ 1][ 0]=0, gain[ 1][ 1 ]=-1（变成颜色1收益-1）。 gain[ 2][ 0]=5, gain[ 2][ 1 ]=3。 初始化： dp[ 0][ 0][ 0]=0, dp[ 0][ 0][ 1 ]=-1。 dp[ 1][ 1][ 0]=0, dp[ 1][ 1][ 1 ]=-1。 len=2, i=0,j=1： 先计算 c0=0： k=0: dp[ 0][ 0][ 0]+dp[ 1][ 1][ 0]+gain[ 2][ 0] = 0+0+5=5 → dp[ 0][ 1][ 0 ]=5。 c0=1： k=0: dp[ 0][ 0][ 1]+dp[ 1][ 1][ 1]+gain[ 2][ 1] = (-1)+(-1)+3=1 → dp[ 0][ 1][ 1 ]=1。 再通过 c0 更新 c： c=0: dp[ 0][ 1][ 0]+gain[ 2][ 0]=5+5=10, dp[ 0][ 1][ 1]+gain[ 2][ 0 ]=1+5=6 → max=10。 但注意这里 len=2，gain[ 2][ 0] 是5，所以 dp[ 0][ 1][ 0 ] 本身已包含这个收益，会重复加，所以这个转移需要调整，避免重复加收益。 实际上方程 (1) 应该是： dp[i][j][c] = max{ dp[i][j][c0] - gain[len][c0]? } 这样不对，因为 dp[ i][ j][ c0] 可能已经包含最后一步 gain[ len][ c0 ] 的收益。 这样会有重复计算，所以标准做法是不用方程 (1)，只用方程 (2)，但这样无法处理最后一步变颜色的情况。 11. 修正 我们允许最后一步变色，所以应该用： dp[i][j][c] = max{ same[i][j][c0] + gain[len][c] } ，其中 same[ i][ j][ c0] 是区间合并成颜色 c0 的 一个方块 的最大收益，但注意这个收益不包含最后一步变成 c0 的 gain。 但 dp[ i][ j][ c0] 已经包含最后一步变成 c0 的 gain，所以 same[ i][ j][ c0] 应该等于 dp[ i][ j][ c0] - gain[ len][ c0 ]。 所以： dp[i][j][c] = max{ dp[i][j][c0] - gain[len][c0] + gain[len][c] } 。 这样避免重复。 所以步骤改为： 先计算 dp[ i][ j][ c0] 用方程 (2)（合并两个同色块），然后对所有 c0, c 用上式更新 dp[ i][ j][ c ]。 12. 最终算法 初始化： dp[ i][ i][ c] = (c == colors[ i]) ? 0 : gain[ 1][ c ]。 转移： 对每个区间 [ i,j ]，每种颜色 c0： dp[ i][ j][ c0] = max{ dp[ i][ k][ c0] + dp[ k+1][ j][ c0] + gain[ 2][ c0 ] } 对 k 从 i 到 j-1。 然后对每种颜色 c： dp[ i][ j][ c] = max{ dp[ i][ j][ c], dp[ i][ j][ c0] - gain[ len][ c0] + gain[ len][ c ] } 对所有 c0。 注意：当 len=1 时，gain[ 1][ c ] 已用。 最终答案 = max{ dp[ 0][ n-1][ c ] }。 这样就能正确处理合并与变色。 13. 总结 本题是区间 DP 的复杂变种，核心是 三维状态 表示区间合并成某种颜色一个方块的最大收益，转移时考虑最后一步是合并两个同色块，以及最后一步变色。 通过先合并成同色块，再变色，覆盖所有可能操作。