USACO 2021 February Gold. Modern Art 3

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

const int NMAX = 305;
const int MOD = 1e9+7;

int n;
int a[NMAX];
int dp[NMAX][NMAX];

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i];
      if (a[i] == a[i - 1]) {
         i--;
         n--;
      }
   }
}

int solve() {
   for (int len = 1; len <= n; len++) {
      for (int l = 1; l + len - 1 <= n; l++) {
         int r = l + len - 1;

         if (len == 1) {
            dp[l][l] = 1;
            continue;
         }

         dp[l][r] = NMAX;
         for (int k = l + 1; k <= r; k++) {
            dp[l][r] = min(dp[l][r], dp[l][k - 1] + dp[k][r] - (a[l] == a[k]));
         }
      }
   }

   return dp[1][n];
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   cout << solve() << endl;

   return 0;
}