Light OJ 1044 / Palindrome Partition - DP

/***
 created: 2022-04-12-16.19.54
***/


#include <bits/stdc++.h>
using namespace std;
#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'

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

    test
    {
        string a;

        cin>>a;

        ll n,m,i,j,k,l;

        n=a.size();

        bool pal[n+4][n+4];

        memset(pal,0,sizeof pal);

        for(i=0;i<n;i++) pal[i][i]=1;

        for(i=0;i<n-1;i++)
        {
            if(a[i]==a[i+1]) pal[i][i+1]=1;
        }

        for(ll len=3;len<=n;len++)
        {
            for(i=0;i<n-len+1;i++)
            {
                j=i+len-1;

                if(a[i]==a[j] && pal[i+1][j-1])
                {
                    pal[i][j]=1;
                }
            }
        }

        ll ans[n+4]={0};

        for(i=0;i<n;i++)
        {
            ll x=INT_MAX;

            if(pal[0][i]==1) ans[i]=0;
            else
            {
                for(j=0;j<i;j++)
                {
                    if(pal[j+1][i]==1 && x>ans[j]+1)
                    {
                        x=ans[j]+1;
                    }
                }
                ans[i]=x;
            }
        }

        cout<<"Case "<<cs<<": "<<ans[n-1]+1<<nl;


    }

    get_lost_idiot;
}


/*

#include <bits/stdc++.h>
using namespace std;
#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<<"Case "<<cs<<": "<<solve(0)<<nl;
    }

    get_lost_idiot;
}

*/