Light OJ 1422 / Interval DP - MCM

/***
 created: 2023-02-22-00.30.35
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'

ll dp[101][101],v[101][101],a[101],n,cnt=1;

ll solve(ll i,ll j)
{
    if(dp[i][j]!=-1) return dp[i][j];
    if(i==j) return 1;
    if(i>j) return 0;
    ll ans=1+solve(i+1,j);
    for(ll in=i+1;in<=j;in++)
    {
        if(a[in]==a[i])
        {
            ans=min(ans,solve(i+1,in)+solve(in+1,j));
        }
    }
    //v[i][j]=cnt;
    return dp[i][j]=ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        cin>>n;
        for(ll i=0;i<n;i++) cin>>a[i];
        //cnt++;
        memset(dp,-1,sizeof dp);
        cout<<"Case "<<cs<<": " <<solve(0,n-1)<<nl;
    }
    return 0;
}