include <bits/stdc++.h>

define inf 0x3f3f3f3f

using namespace std;
const int maxn=550;
typedef long long ll;
int dp[maxn][maxn],val[maxn][maxn];

int main(){
int n;
scanf("%d",&n);
memset(dp,inf,sizeof(dp));
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
dp[i][i]=1,val[i][i]=x;
}
for(int len=1;len<=n;len++){
for(int j=1;j+len<=n+1;j++){
int ends=j+len-1;
for(int i=j;i<ends;i++){
if(dp[j][i]1&&dp[i+1][ends]1&&val[j][i]==val[i+1][ends]){
dp[j][ends]=1;val[j][ends]=val[j][i]+1;
}
else dp[j][ends]=min(dp[j][ends],dp[j][i]+dp[i+1][ends]);
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}

Educational Codeforces Round 83 E. Array Shrinking

原文：https://www.cnblogs.com/EchoZQN/p/12577914.html