पायथन में किसी दिए गए स्ट्रिंग को बनाने के लिए न्यूनतम लागत निर्धारित करने का कार्यक्रम

मान लीजिए, हमें एक स्ट्रिंग 'str' बनानी है जिसकी लंबाई n है। स्ट्रिंग बनाने के लिए, हम दो ऑपरेशन कर सकते हैं।

लागत a के लिए str के अंत में एक वर्ण जोड़ा जा सकता है।
कॉस्ट r के लिए str के अंत में एक सबस्ट्रिंग sub_str जोड़ा जा सकता है।

हमें स्ट्रिंग स्ट्र के निर्माण की न्यूनतम लागत की गणना करनी होगी।

इसलिए, यदि इनपुट a =5, r =4, str ='tpoint' जैसा है, तो आउटपुट 29 होगा।

स्ट्रिंग 'टपॉइंट' बनाने के लिए, लागत नीचे वर्णित है -

str = 't'; a new character added, therefore the cost is 5.
str = 'tp'; a new character added, therefore the cost is 5.
str = 'tpo'; a new character added, therefore the cost is 5.
str = 'tpoi'; a new character added, therefore the cost is 5.
str = 'tpoin'; a new character added, therefore the cost is 5.
str = 'tpoint'; substring 't' is added, therefore the cost is 4.

कुल लागत 5 + 5 + 5 + 5 + 5 + 4 =29 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

आकार :=str का आकार
सबसे बड़ी :=एक नई सूची
निम्न :=0
1 से आकार+1 तक के अप के लिए, करें
- जबकि str[सूचकांक निम्न से अनुक्रमणिका upp तक] str में मौजूद नहीं है [सूचकांक 0 से अनुक्रमणिका निम्न तक], करें
  - निम्न :=कम + 1
- सबसे बड़े के अंत में (ऊपर - नीचे) डालें
c :=एक नई सूची जिसमें एक है
1 से लेकर आकार तक के i के लिए, करें
- यदि सबसे बड़ा[i] 0 के समान है, तो
  - c के अंत में (c + a का अंतिम तत्व) डालें
- अन्यथा,
  - c के अंत में कम से कम (c + a का अंतिम तत्व), (c[i - सबसे बड़ा[i]] + r) डालें
c का अंतिम तत्व लौटाएं

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(a, r, str):
   size = len(str)
   largest = []
   low = 0
   for upp in range(1, size+1):
      while str[low:upp] not in str[:low]:
         low += 1
      largest.append(upp - low)

   c = [a]
   for i in range(1, size):
      if largest[i] == 0:
         c.append(c[-1] + a)
      else:
         c.append(min(c[-1] + a, c[i - largest[i]] + r))

   return c[-1]

print(solve(5, 4, 'tpoint'))

इनपुट

5, 4, 'tpoint'