一道非常基础的区间DP，因为肯定是全部染成里面有的颜色比较快，所以我们只要对每个已经同色的块向外扩张就行了。
转移方程：
dp[i][j]表示i,j区间内都染成同色的最小步骤。
dp[i][j]=min(dp[i][j],dp[i+1][j]+(a[i]!=a[i+1]),dp[i][j-1]+(a[j]!=a[j-1]),dp[i+1][j-1]+2-(a[i]==a[r]));
下附代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int INF=0X3f3f3f3f; 4 int dp[5005][5005],a[5005],n; 5 int main(){ 6 memset(dp,INF,sizeof(dp)); 7 scanf("%d",&n); 8 for (int i=1; i<=n; i++){ 9 scanf("%d",&a[i]); 10 dp[i][i]=0; 11 } 12 for (int len=2; len<=n; len++){ 13 for (int l=1; l+len-1<=n; l++){ 14 int r=l+len-1; 15 if (a[r]==a[r-1]) dp[l][r]=min(dp[l][r],dp[l][r-1]); 16 else dp[l][r]=min(dp[l][r],dp[l][r-1]+1); 17 if (a[l]==a[l+1]) dp[l][r]=min(dp[l][r],dp[l+1][r]); 18 else dp[l][r]=min(dp[l][r],dp[l+1][r]+1); 19 if (a[l]==a[r]) dp[l][r]=min(dp[l][r],dp[l+1][r-1]+1); 20 } 21 } 22 printf("%d",dp[1][n]); 23 }
PS：区间DP掌握的不是很好，这基本上是一个入门题，还被卡了很久，需要多加练习
原文：https://www.cnblogs.com/i-caigou-TT/p/14052591.html
