题目大概是依次有n场派对，每场派对都有需要穿某套衣服去参加，可以同时穿多套衣服，就是一套套着一套，如果脱了的话就不能再穿上那套了，问最少需要几套衣服去参加完所有派对。
区间DP：
转移是这样考虑的：如果第j场另外穿一件就有dp[i][j]=dp[i][j-1]+1；否则就是第k场（i<=k<j，且第k场衣服与第j场相同）的衣服不脱下来一直到第j场，就有dp[i][j]=dp[i][k]+dp[k+1][j-1]。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int d[111][111]; 6 int main(){ 7 int t,n,a[111]; 8 scanf("%d",&t); 9 for(int cse=1; cse<=t; ++cse){ 10 scanf("%d",&n); 11 for(int i=1; i<=n; ++i) scanf("%d",a+i); 12 memset(d,0,sizeof(d)); 13 for(int i=1; i<=n; ++i) d[i][i]=1; 14 for(int len=2; len<=n; ++len){ 15 for(int i=1; i+len-1<=n; ++i){ 16 d[i][i+len-1]=d[i][i+len-2]+1; 17 for(int j=i; j<i+len-1; ++j){ 18 if(a[j]==a[i+len-1]) d[i][i+len-1]=min(d[i][i+len-1],d[i][j]+d[j+1][i+len-2]); 19 } 20 } 21 } 22 printf("Case %d: %d\n",cse,d[1][n]); 23 } 24 return 0; 25 }
LightOJ1422 Halloween Costumes（区间DP）
原文：http://www.cnblogs.com/WABoss/p/5164744.html