动态变化数组相邻相等合并后剩余最小元素个数求解

你之前用链表反复遍历的暴力方案最坏时间复杂度为O(n²)，且如果固定合并顺序容易错过最优解，这里推荐使用区间动态规划方案，时间复杂度O(n³)，可以覆盖所有合法合并场景，得到准确的最小长度。

注意：不要尝试用从左到右合并的贪心栈思路，存在反例：数组[1,1,1,2,2,2]用贪心栈得到的最小长度是4，但实际最优解是先合并后两个1、再合并所有连续2，最终可以得到长度为2的[1,4]，贪心逻辑无法覆盖这种需要调整合并顺序的场景。

核心状态定义 #

假设原数组下标从0开始，总长度为n，我们定义两个二维数组辅助计算：

• dp[l][r]：原数组下标l到r的闭区间，经过任意次合并后能得到的最小元素个数
• val[l][r]：如果区间[l,r]可以合并为单个元素，该值存储合并后的数值，否则存-1作为无效标记

初始化规则 #

所有长度为1的区间（即l == r的情况）：

• dp[l][r] = 1，单个元素无需合并，长度固定为1
• val[l][r] = arr[l]，单个元素的数值就是原数组对应位置的值

状态转移规则 #

我们从小到大枚举区间长度len（从2到n）：

1. 遍历所有合法左端点l，计算对应右端点r = l + len - 1
2. 先初始化dp[l][r]为最坏情况：枚举所有分割点k（l ≤ k < r），取dp[l][k] + dp[k+1][r]的最小值，此时默认左右两个子区间无法进一步合并
3. 再判断是否存在跨子区间合并的可能：如果存在某个分割点k，同时满足val[l][k] != -1、val[k+1][r] != -1、val[l][k] == val[k+1][r]，说明左右两个子区间都可以合并为单个元素且数值相等，还能再次合并，此时更新dp[l][r] = 1，val[l][r] = val[l][k] + 1

最终结果 #

整个数组的最小合并长度就是dp[0][n-1]

示例验证 #

以你给出的[1,1,1,2,1]为例：

• 计算区间[0,2]（三个1）时，所有分割点的左右子区间合并后的值都不相等，因此dp[0][2] = 2，val[0][2] = -1
• 计算区间[1,3]（1,1,2）时，前两个1合并为2，和第三个元素2相等，因此可以进一步合并为3，dp[1][3] =1，val[1][3] =3
• 最后整个区间的最小长度为dp[0][0] + dp[1][3] + dp[4][4] = 1+1+1 =3，和示例结果完全一致

优化方向 #

如果数组长度n较大，可以通过记忆化搜索+状态剪枝降低实际运行时间，也可以提前预处理所有可合并为单个元素的区间，把时间复杂度优化到接近O(n²)。

内容的提问来源于stack exchange，提问作者Chessaddict