Halloween Costumes LightOJ - 1422 区间dp

//dp[i][i]=1。也就是说每个舞会换件衣服
//对于dp[i][j]:
//1.如果cos[i]=cos[j]，dp[i][j]=dp[i][j-1]，很明显i的衣服穿在最底，在j的时候就能拿出来再用
//之后枚举中间点k，注意(i<=k<j)。
//如果cos[i]=cos[k]，那么k的衣服就是i的衣服了，那么dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
// 注意这里是dp[i][k]，而不是dp[i][k-1]，因为在此之前，对于i和k，已经进行过上面的1
//那么 dp[i][k] 就已经是当前最优状况 
#include<iostream>
#include<cstdio> 
#include<cstring>
using namespace std;
#define maxn 105
#define inf 0x3f3f3f3f
int a[105],dp[105][105];
int main() {
    int T,n,no=0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) 
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++) 
            dp[i][i]=1;
        for(int p=1; p<=n; p++) {
            for(int i=1; i<=n; i++) {
                int j=i+p;
                dp[i][j]=inf;
                if(a[i]==a[j]) 
                    dp[i][j]=dp[i][j-1];
                for(int k=i; k<j; k++)
                    if(a[i]==a[k]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
        printf("Case %d: %d\n",++no,dp[1][n]);
        memset(dp,0,sizeof(dp));
    }
}

Halloween Costumes LightOJ - 1422 区间dp

原文：https://www.cnblogs.com/QingyuYYYYY/p/12466773.html