पायथन में स्टोन गेम में अधिकतम स्कोर खोजने का कार्यक्रम

मान लीजिए कि एक पंक्ति में कई पत्थर रखे गए हैं, और इनमें से प्रत्येक पत्थर की एक संबद्ध संख्या है, जो एक सरणी स्टोनवैल्यू में दी गई है। अमल प्रत्येक दौर में पंक्ति को दो भागों में विभाजित करता है फिर बिमल प्रत्येक भाग के मूल्य की गणना करता है जो इस भाग के सभी पत्थरों के मूल्यों का योग है। बिमल उस भाग को फेंक देता है जिसका मूल्य अधिकतम होता है, और अमल का अंक शेष भाग के मूल्य से बढ़ जाता है। जब दो भागों के मान समान होते हैं, तो बिमल अमल को तय करने देता है कि कौन सा हिस्सा फेंक दिया जाएगा। अगला दौर शेष भाग से शुरू होता है। खेल समाप्त होता है जब केवल एक पत्थर शेष रहता है। हमें अमल द्वारा प्राप्त किए जा सकने वाले अधिकतम अंक प्राप्त करने होंगे।

इसलिए, यदि इनपुट स्टोनवैल्यू =[7,3,4,5,6,6] जैसा है, तो आउटपुट होगा

राउंड 1 पर, अमल पंक्ति को [7,3,4], [5,6,6] की तरह विभाजित करता है। बायीं पंक्ति का योग 14 है और दाहिनी पंक्ति का योग 17 है। बिमल दायीं पंक्ति को फेंक देता है और अमल का स्कोर अब 14 है।
राउंड 2 में, अमल पंक्ति को [7], [3,4] में विभाजित करता है। तो बिमल बाईं पंक्ति को फेंक देता है और अमल का स्कोर (14 + 7) =21 हो जाता है।
तीसरे दौर में, अमल के पास पंक्ति को विभाजित करने के लिए केवल एक विकल्प है जो [3], [4] है। बिमल दाहिनी पंक्ति को फेंक देता है और अमल का स्कोर अब (21 + 3) =24 है।

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

फ़ंक्शन को परिभाषित करें dfs() । यह शुरू होगा, खत्म होगा
अगर प्रारंभ>=अंत, तो
- वापसी 0
max_score :=0
सीमा में कटौती के लिए प्रारंभ से अंत तक, करें
- sum1 :=partial_sum[शुरू, कट]
- sum2 :=partial_sum[cut+1, end]
- अगर sum1> sum2 , तो
  - स्कोर :=sum2 + dfs(कट+1, अंत)
- अन्यथा जब sum1
  - स्कोर :=sum1 + dfs (स्टार्ट, कट)
- अन्यथा,
  - स्कोर :=sum1 + अधिकतम dfs (स्टार्ट, कट) और dfs (कट+1, एंड)
- max_score :=अधिकतम स्कोर और max_score
वापसी max_score
एक फ़ंक्शन को परिभाषित करें getPartialSum() । इसमें लगेगा
मैं के लिए 0 से n -1 की सीमा में, करो
- Partial_sum[i, i] :=StoneValue[i]
मैं के लिए 0 से n -1 की सीमा में, करो
- i+1 से n-1 की श्रेणी में j के लिए, करें
  - Partial_sum[i, j] :=partial_sum[i, j-1] + StoneValue[j]
मुख्य विधि से, निम्न कार्य करें
n :=पत्थर के आकार का मान
part_sum :=n x n आकार का एक वर्गाकार सरणी और 0
. से भरा हुआ
getPartialSum ()
वापसी dfs(0, n-1)

उदाहरण

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

def solve(stoneValue):
   def dfs(start, end):
      if start >= end:
         return 0
      max_score = 0

      for cut in range(start, end):
         sum1 = partial_sum[start][cut]
         sum2 = partial_sum[cut+1][end]
         if sum1 > sum2:
            score = sum2+dfs(cut+1, end)
         elif sum1 < sum2:
            score = sum1+dfs(start, cut)
         else:
            score = sum1+max(dfs(start, cut), dfs(cut+1, end))
            max_score = max(score, max_score)
      return max_score


   def getPartialSum():
      for i in range(n):
         partial_sum[i][i] = stoneValue[i]
      for i in range(n):
         for j in range(i+1, n):
            partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]


   n = len(stoneValue)
   partial_sum = [[0]*n for _ in range(n)]
   getPartialSum()
   return dfs(0, n-1)

stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))

इनपुट

[7,3,4,5,6,6]