DP Ⅲ

#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x = 0; bool f = 0; char ch = getchar();
	while('0' > ch || ch > '9') { if(ch == '-') f = !f; ch = getchar(); }
	while('0' <= ch && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	x = f ? -x : x; return;
}
template <typename T> inline void print(T x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0'); return;
}
const int N = 510;
int f[N][N], a[N], n;
int main()
{
	read(n);
	for(int i = 1; i <= n; i ++) read(a[i]);
	memset(f, 0x3f, sizeof(f));
	for(int i = 1; i <= n; i ++) f[i][i] = 1;
	for(int len = 2; len <= n; len ++)
	{
		for(int i = 1; i <= n - len + 1; i ++)
		{
			int j = i + len - 1;
			for(int k = i; k < j; k ++)
			{
				if(a[i] == a[j])
				{
					if(i == j - 1) f[i][j] = 1;
					else f[i][j] = min(f[i][j], f[i + 1][j - 1]);
				}
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
			}
		}
	}
	print(f[1][n]);
	return 0;
}