D. 洪水填充 详细题解

题目核心理解

给定一行 $n$ 个带颜色的方格，同一种颜色的连续一段称为一个连通块。 游戏规则如下：

1. 一开始任选一个起点方格（不计操作次数）。
2. 每一步可以把起点所在连通块整体染成任意其他颜色。

求把整行方格变成同一种颜色所需的最少操作次数。

数据范围：

• $1 \le n \le 5000$
• $1 \le c_i \le 5000$

---

核心思路

1. 关键性质

• 连续相同颜色不影响答案，可以先去重压缩，得到相邻颜色互不相同的新数组。
• 最优策略等价于：从某个中心开始，用最少步数向左右“吞并”相邻区块。
• 若压缩后长度为 $m$，则最多需要 $m-1$ 步；能匹配到的相同颜色越多，步数越少。

2. 区间 DP 定义

设压缩后数组为 $a[0..m-1]$。 定义 $dp[l][r]$ 为：把区间 $[l, r]$ 染成同一种颜色的最少操作次数。

3. 转移规则

• 若 $a[l] = a[r]$： 右端点可以直接被左侧区间“带成同色”，因此$$dp[l][r] = dp[l][r-1]$$
• 若 $a[l] \neq a[r]$： 只能从左边或右边扩展一步，因此$$dp[l][r] = \min(dp[l+1][r], dp[l][r-1]) + 1$$

---

算法流程

1. 读入颜色数组，压缩连续相同颜色，得到新数组 $a$，长度为 $m$。
2. 初始化：$dp[i][i] = 0$，单个格子不需要操作。
3. 按区间长度从小到大枚举 $len$，再枚举左端点 $l$，算出右端点 $r$。
4. 按上述转移式计算 $dp[l][r]$。
5. 最终答案为 $dp[0][m-1]$。

---

公式与复杂度分析

核心转移：

$$dp[l][r] = \begin{cases} dp[l][r-1], & a[l]=a[r] \\ \min(dp[l+1][r], dp[l][r-1])+1, & a[l]\neq a[r] \end{cases} $$

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

可在 $n \le 5000$ 范围内稳定运行，完全满足题目限制。