একটি ইনপুট স্ট্রিং দেওয়া আছে। স্ট্রিংকে প্যালিনড্রোম সাবস্ট্রিংগুলোর মধ্যে পার্টিশন করতে হবে। মিনিমাম কত কাট দরকার সেটা বের করতে হবে।
উদাহরণ: "ababbbabbababa" -> ৩ কাট দরকার (a | babbbab | b | ababa)।
সমাধান: DP ব্যবহার। cut[i][j] = i থেকে j পর্যন্ত মিনিমাম কাট। pal[i][j] = i থেকে j প্যালিনড্রোম কিনা। লেন্থ ২ থেকে n পর্যন্ত সব সাবস্ট্রিং চেক করে DP টেবিল ফিল।
উদাহরণ
#include <iostream>
#include <climits>
using namespace std;
int min (int a, int b){
return (a < b)? a : b;
}
int minPalPartion(string str){
int n = str.size();
int cut[n][n];
bool pal[n][n];
for (int i=0; i
ইনপুট
ababbbabbababa
আউটপুট
Min cuts for Palindrome Partitioning is: 3
