LightOj 1422 Halloween Costumes 两种姿势详解（区间DP）

#include<iostream>
#include<string.h>
using namespace std;
int a[200];int dp[200][200];

int main(){
	int t;cin>>t;
	int cn=1;
	while(t--){
		memset(dp,0,sizeof(dp));
		int n;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 l=1;l+len-1<=n;l++){
				int r=l+len-1;
				dp[l][r]=dp[l][r-1]+1;
				for(int k=l;k<r;k++){
					if(a[r]==a[k])
					dp[l][r]=min(dp[l][k]+dp[k+1][r-1],dp[l][r]);
				}
			}
		}
		printf("Case %d: ",cn++);
		cout<<dp[1][n]<<endl;
	}
} 

学长博客：https://blog.csdn.net/qq_34374664/article/details/54867113