ধরুন, আমাদের একটি স্ট্রিং 'str' তৈরি করতে হবে যেটির দৈর্ঘ্য n। স্ট্রিং তৈরি করতে, আমরা দুটি অপারেশন করতে পারি।
- কস্ট a এর জন্য str এর শেষে একটি অক্ষর যোগ করা যেতে পারে।
- মূল্য r এর জন্য str এর শেষে একটি সাবস্ট্রিং sub_str যোগ করা যেতে পারে।
আমাদের স্ট্রিং স্ট্রিং নির্মাণের সর্বনিম্ন খরচ গণনা করতে হবে।
সুতরাং, যদি ইনপুটটি a =5, r =4, str ='tpoint' এর মত হয়, তাহলে আউটপুট হবে 29।
স্ট্রিং 'tpoint' তৈরি করতে, খরচ নীচে বর্ণনা করা হয়েছে −
str ='t'; একটি নতুন অক্ষর যোগ করা হয়েছে, তাই খরচ হল 5.str ='tp'; একটি নতুন অক্ষর যোগ করা হয়েছে, তাই খরচ হল 5.str ='tpo'; একটি নতুন অক্ষর যোগ করা হয়েছে, তাই খরচ হল 5.str ='tpoi'; একটি নতুন অক্ষর যোগ করা হয়েছে, তাই খরচ হল 5.str ='tpoin'; একটি নতুন অক্ষর যোগ করা হয়েছে, তাই খরচ হল 5.str ='tpoint'; সাবস্ট্রিং 't' যোগ করা হয়েছে, তাই খরচ হল 4।
মোট খরচ 5 + 5 + 5 + 5 + 5 + 4 =29।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- size :=str এর আকার
- সবচেয়ে বড় :=একটি নতুন তালিকা
- কম :=0
- রেঞ্জ 1 থেকে সাইজ+1 এর জন্য,
- করুন
- যদিও str[index low থেকে index upp] str[index 0 থেকে index low]-এ থাকে না, কর
- low :=low + 1
- সর্ববৃহৎ শেষে সন্নিবেশ (উর্ধ্ব-নিম্ন)
- যদিও str[index low থেকে index upp] str[index 0 থেকে index low]-এ থাকে না, কর
- c :=একটি ধারণকারী একটি নতুন তালিকা
- আমি রেঞ্জ 1 থেকে আকারের জন্য, কর
- যদি বৃহত্তম[i] 0 এর সমান হয়, তাহলে
- c এর শেষে সন্নিবেশ করুন (c + a এর শেষ উপাদান)
- অন্যথায়,
- c এর শেষে ন্যূনতম (c + a এর শেষ উপাদান), (c[i - বৃহত্তম[i]] + r) সন্নিবেশ করুন
- যদি বৃহত্তম[i] 0 এর সমান হয়, তাহলে
- c এর শেষ উপাদানটি ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(a, r, str):size =len(str) large =[] low =0 upp in range(1, size+1):যখন str[low:upp] str[:-এ নয় low]:low +=1 large.append(upp - low) c =[a] i-এর জন্য রেঞ্জ(1, size):if large[i] ==0:c.append(c[-1] + a ) else:c.append(min(c[-1] + a, c[i - বৃহত্তম[i]] + r)) রিটার্ন c[-1]print(solve(5, 4, 'tpoint'))ইনপুট
5, 4, 'tpoint'আউটপুট
২৯
