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

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

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

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

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

एक फ़ंक्शन dfs() परिभाषित करें। यह start, end लेगा
यदि start >= end, तो
- 0 वापस करें
max_score := 0
cut को start से end तक के लिए, करें
- sum1 := partial_sum[start, cut]
- sum2 := partial_sum[cut+1, end]
- यदि sum1 > sum2, तो
  - score := sum2 + dfs(cut+1, end)
- अन्यथा जब sum1 < sum2, तो
  - score := sum1 + dfs(start, cut)
- अन्यथा,
  - score := sum1 + dfs(start, cut) और dfs(cut+1, end) का अधिकतम
- max_score := score और max_score का अधिकतम
max_score वापस करें
एक फ़ंक्शन getPartialSum() परिभाषित करें। यह लेगा
i को 0 से n - 1 तक के लिए, करें
- partial_sum[i, i] := stoneValue[i]
i को 0 से n - 1 तक के लिए, करें
- j को i+1 से n - 1 तक के लिए, करें
  - partial_sum[i, j] := partial_sum[i, j-1] + stoneValue[j]
मुख्य विधि से, निम्न करें
- n := stoneValue का आकार
- partial_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]