题意大概是这样，第i天必须穿a[i]（某一种类）的衣服，你可以套着穿很多件，对于第i天，你有两种操作，一种是脱掉现在的衣服，一种是穿上新的一件，但是你脱掉的衣服，以后不能再穿。问最少需要多少件衣服？
没点脑子还真想不出来是区间DP。。。
这样考虑，首先我们初始化DP，假设每个地方都不一样，那么DP[i][j]=j-i+1
然后考虑怎么转移。
假设a[i] == a[j]
那么我们我知道，这一步其实是不费任何力气的，因为我以前穿了i后现在不用穿新的了。
那么dp[i][j]=min(dp[i][j-1],dp[i+1][j])
否则的话dp[i][j]=min(dp[i][j-1]+1,dp[i+1][j]+1)
我觉得必须要取最小值，因为dp[i][j]代表的区间所需要最小种类可能来自左右两个不同方向传递过来。
当然最后转移的时候，还是非常简单的，考虑k为分割点，那么值可能是由两边的值传递过来的。
当然有人会问，明显dp[i][k]的种类可能和dp[k+1][j]的种类有重合，这怎么办呢？？？其实并没有关系，如果重合了，那么在我们遍历区间内的间断点的时候，在某个时间段，一定把这个种类包含在内了，而我们在上面维护的时候，已经处理了相等的问题，所以不用考虑。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
int a[];
int dp[][];
int main(){
int t,n;
int ca=;
scanf("%d",&t);
while(t--){
memset(dp,,sizeof(dp));
scanf("%d",&n);
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for (int i=;i<=n;i++){
for (int j=i;j<=n;j++){
dp[i][j]=j-i+;
}
}
for (int len=;len<=n;len++){
for (int i=;i+len-<=n;i++){
int j=i+len-;
if (a[i]==a[j]){
dp[i][j]=min(dp[i][j-],dp[i+][j]);
}else {
dp[i][j]=min(dp[i][j-]+,dp[i+][j]+);
}
for (int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
}
// cout<<dp[1][6]<<endl;
printf("Case %d: %d\n",ca++,dp[][n]);
}
return ;
}