[kuangbin带你飞]专题二十二 区间DP-B-LightOJ - 1422
题意大概是这样，第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[105]; int dp[105][105]; int main(){ int t,n; int ca=1; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } for (int i=1;i<=n;i++){ for (int j=i;j<=n;j++){ dp[i][j]=j-i+1; } } for (int len=2;len<=n;len++){ for (int i=1;i+len-1<=n;i++){ int j=i+len-1; if (a[i]==a[j]){ dp[i][j]=min(dp[i][j-1],dp[i+1][j]); }else { dp[i][j]=min(dp[i][j-1]+1,dp[i+1][j]+1); } for (int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } } // cout<<dp[1][6]<<endl; printf("Case %d: %d\n",ca++,dp[1][n]); } return 0; }
