1312E - Array Shrinking - CodeForces Solution

// Problem: E. Array Shrinking
// Contest: Codeforces - Educational Codeforces Round 83 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1312/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
const int N =500+10;
int dp[N][N],v[N][N];
signed main (){
	std::ios::sync_with_stdio(false);  
	cin.tie(NULL); 
	cout.tie(NULL);
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>v[i][i];
	}
	for(int i=2;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			int r=j+i-1;
			if(r>n)
			break;
			
			
			for(int k=j;k<r;k++)
			{	//if(i==1)
			//cout<<i<<endl;
				dp[j][r]=max(dp[j][r],dp[j][k]+dp[k+1][r]);
				if(v[j][k]==v[k+1][r]&&v[j][k]!=0)
				{
					dp[j][r]=i-1;
					v[j][r]=v[j][k]+1;
					
				}
			}
		}
	cout<<n-dp[1][n]<<endl;
	
}