C++ এ একটি প্রদত্ত স্ট্রিংয়ের সর্বাধিক ওজন রূপান্তর

সমস্যা বিবৃতি

শুধুমাত্র A এবং B এর সমন্বয়ে একটি স্ট্রিং দেওয়া হয়েছে। আমরা যে কোনো অক্ষর টগল করে প্রদত্ত স্ট্রিংটিকে অন্য স্ট্রিংয়ে রূপান্তর করতে পারি। এইভাবে প্রদত্ত স্ট্রিং এর অনেক রূপান্তর সম্ভব। কাজ হল সর্বাধিক ওজন রূপান্তরের ওজন খুঁজে বের করা।

নিচের সূত্র −

ব্যবহার করে একটি স্টিং এর ওজন গণনা করা হয়

স্ট্রিংয়ের ওজন =মোট জোড়ার ওজন + একক অক্ষরের ওজন - টগলের মোট সংখ্যা।

পরপর দুটি অক্ষর আলাদা হলেই জোড়া বলে বিবেচিত হয়।
এক জোড়ার ওজন (উভয় অক্ষরই আলাদা) =4
একটি একক অক্ষরের ওজন =1

যদি ইনপুট স্ট্রিং − "AA" হয় তাহলে আউটপুট হবে 3 −

প্রদত্ত স্ট্রিং এর রূপান্তরগুলি হল "AA", "AB", "BA" এবং "BB"।
সর্বাধিক ওজন রূপান্তর হল "AB" বা "BA"। এবং ওজন হল "এক জোড়া - এক টগল" =4-1 =3।

অ্যালগরিদম

<পূর্ব>1. যদি (n ==1) সর্বোচ্চ ওজন(str[0..n-1]) =12. অন্যথায় যদি str[0] !=str[1] maxWeight(str[0..n-1]) =সর্বোচ্চ (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1])3. বাকি maxWeight(str[0..n-1]) =সর্বোচ্চ (1 + সর্বোচ্চ ওজন( str[1..n-1]), 3 + getMaxRec(str[2..n-1])

উদাহরণ

#includeনেমস্পেস ব্যবহার করে std;int getMaxRec(string &str, int i, int n, int lookup[]){ if (i>=n) { return 0; } if (lookup[i] !=-1) { return lookup[i]; } int ans =1 + getMaxRec(str, i + 1, n, lookup); if (i + 1 আউটপুট যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে ফলাফল =3