প্যালিনড্রোম পার্টিশনিং II সমস্যা
একটি স্ট্রিং s দেওয়া আছে। এটিকে কতগুলো কাট দিয়ে প্যালিনড্রোম সাবস্ট্রিং-এ ভাগ করা সম্ভব? ন্যূনতম কত কাট দরকার?
উদাহরণ: "ababba" → ২ কাট (aba|bb|a)
সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
n = s.length()res[i]= সূচকiথেকে শেষ পর্যন্ত প্যালিনড্রোম পার্টিশনে ন্যূনতম কাটres[n] = -1(বেস কেস)for i = n-1 down to 0:res[i] = n - i - 1(সর্বোচ্চ সম্ভব কাট)for j = i to n-1:- যদি
s[i..j]প্যালিনড্রোম হয়, তবেres[i] = min(res[i], 1 + res[j+1])
- যদি
res[0]ফেরত দিন
প্যালিনড্রোম চেক O(n) → মোট O(n³)। প্রি-কম্পিউট প্যালিনড্রোম টেবিল দিয়ে O(n²) সম্ভব।
C++ কোড উদাহরণ
ইনপুট
"ababba"আউটপুট
2
