#include<bits/stdc++.h>
using namespace std;
int a[5007];
int dp[5007][5007];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
n=unique(a+1,a+1+n)-a-1;
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++){
dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);//右面变为左面的颜色或者左面变为右面的颜色
if(a[i]==a[j])
dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);//里面变为外面的颜色
}
}
printf("%d",dp[1][n]);
return 0;
Codeforces Round #538 (Div. 2)D（区间DP，思维）
原文：https://www.cnblogs.com/ldudxy/p/10412855.html