UVA 11584 / Edit distance

/***
 created: 2022-06-19-01.02.10
***/

#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 test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll dp[1005];
string a;

bool checkPal(ll i,ll j)
{
    while(i<j)
    {
        if(a[i]!=a[j]) return 0;

        i++;
        j--;
    }
    return  1;
}

ll solve(ll in)
{
    if(dp[in]!=-1) return dp[in];

    if(in>=a.size()) return 0;

    ll ans=INT_MAX;

    for(ll i=in;i<a.size();i++)
    {
        if(checkPal(in,i))
        {
            ans=min(ans,1+solve(i+1));
        }
    }

    return dp[in]=ans;
}

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

    test
    {
        cin>>a;

        memset(dp,-1,sizeof dp);

        cout<<solve(0)<<nl;
    }

    get_lost_idiot;
}