Wednesday, 08 December, 2021

Rifat's Blog

Competitive Programming Notebook

single post

  • Home
  • Lightoj-1033 Generating Palindromes
DP, LightOJ, Solve By OJ, Solve By Topic

Lightoj-1033 Generating Palindromes

Problem NameGenerating Palindromes
JudgeLightoj
Problem Linkhttps://lightoj.com/problem/generating-palindromes
Algorithms & DSDynamic Programming , LCS
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sf(n) scanf("%lld",&n);
#define YES printf("YES\n");
#define NO printf("NO\n");
#define nl printf("\n");
#define PB push_back
#define VST(V) sort(V.begin(),V.end())
#define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  base1 129
#define  base2 137
#define  MOD1  1479386893
#define  MOD2  1928476349
#define MAX 2000010
ll SET(ll NUM,ll POS)
{
    return NUM | (1<<POS);
}
bool isOn(ll NUM,ll POS)
{
    return (bool)(NUM & (1<<POS));
}
ll mem[110][110];
string s;
ll dp(ll left,ll right){
    if(left>=right){
        return 0;
    }
    if(mem[left][right]!=-1){
        return mem[left][right];
    }
    ll ans=0;
    if(s[left]==s[right]){
        ans=dp(left+1,right-1);
    }
    else{
        ans=dp(left+1,right)+1;
        ans=min(ans,dp(left,right-1)+1);
    }
    return mem[left][right]=ans;
}
int main()
{
    //freopen("1input.txt","r",stdin);
    fast;
    ll tcase=1;
    cin>>tcase;
    for(ll test=1; test<=tcase; test++)
    {

        cin>>s;
        ll n=s.size();
        for(ll i=0;i<=n;i++){
            for(ll j=0;j<=n;j++){
                mem[i][j]=-1;
            }
        }
        ll ans=dp(0,n-1);
        cout<<"Case "<<test<<": "<<ans<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

Created by Abu Rifat Muhammed Al Hasib
2021 © All rights reserved


error: Alert: Content is protected !!