Lightoj-1044 Palindrome Partitioning

L
Problem NamePalindrome Partitioning
JudgeLightoj
Problem Linkhttps://lightoj.com/problem/palindrome-partitioning
Algorithms & DSDynamic Programming
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #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); ll SET(ll NUM,ll POS) { return NUM | (1<<POS); } bool isOn(ll NUM,ll POS) { return (bool)(NUM & (1<<POS)); } string s; ll ck_palindrome(ll l,ll r) { while(l<=r) { if(s[l]!=s[r])return 0; l++; r--; } return 1; } ll mem[1010][1010]; ll dp(ll l,ll r) { if(l>r) { return 0; } if(l==r) { return 1; } if(mem[l][r]!=-1) { return mem[l][r]; } ll ans=LONG_MAX; ans=1+dp(l+1,r); for(ll i=l+1; i<=r; i++) { if(ck_palindrome(l,i)==1) { ans=min(ans,dp(i+1,r)+1); } } return mem[l][r]=ans; } int main() { //freopen("1input.txt","r",stdin); // fast; ll tcase=1; cin>>tcase; for(ll test=1; test<=tcase; test++) { ll n; cin>>s; 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; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!