n 个方块排成一排，第 i 个颜色为 ci。定义一个颜色联通块 [l,r] 当且仅当 l 和 r 之间（包l,r）所有方块的颜色相同。现在你可以选定一个起始位置 p，每次将 p 所在颜色联通块的所有方块颜色改成另一种。这个操作可能将多个颜色联通块合并成一个。问最少要多少步，能让 [1,n] 变成一个颜色联通块。
1≤n,ci≤5000。

经典区间dp问题

题解：dp[i][j] 表示将i-j这个区间合并成同一个联通块的最小步骤
首先要预处理原数组，使得相邻元素不能相等，这样才可以进行区间dp操作

dp[i][j] = min(dp[i][k] + dp[k + 1][j] + 1);

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int a[maxn], c[maxn], dp[maxn][maxn];
int main() {
    int n, tot = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)  {
        cin >> a[i];
        if (a[i] == a[i - 1]) continue;
        c[++tot] = a[i];
    }
    n = tot;
    for (int l = 1; l <= n; l++) {
        for (int i = 1; i + l - 1<= n; i++) {
            int j = i + l - 1;
            if (i == j) {
                dp[i][j] = 0;
            }
            else if (c[i] == c[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 1;
            } else {
                dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}