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

मान लीजिए हमारे पास stones नामक एक सरणी है जहां stones[i] बाएं से i-वें पत्थर का मान दर्शाता है। दो दोस्त अमल और बिमल इन पत्थरों के साथ एक टर्न-आधारित खेल खेल रहे हैं और अमल हमेशा पहले शुरू करता है। n पत्थर एक पंक्ति में व्यवस्थित हैं। प्रत्येक खिलाड़ी पंक्ति से या तो सबसे बाएं पत्थर या सबसे दाएं पत्थर को हटा सकता है और पंक्ति में शेष पत्थरों के मूल्यों के योग के बराबर अंक प्राप्त कर सकता है। जिसका स्कोर अधिक होगा वह जीतेगा। अब, बिमल ने पाया कि वह हमेशा यह खेल हार जाएगा, इसलिए उसने स्कोर के अंतर को कम करने का फैसला किया। अमल का लक्ष्य स्कोर में अंतर को अधिकतम करना है। इसलिए हमें अमल और बिमल के स्कोर में अंतर ज्ञात करना है यदि वे दोनों इष्टतम रूप से खेलते हैं।

इसलिए, यदि इनपुट है stones = [6,4,2,5,3], तो आउटपुट 6 होगा क्योंकि अमल 3 ले सकता है, इसलिए उसका स्कोर 6+4+2+5 = 17 होगा, बिमल का स्कोर अब तक 0, और सरणी [6,4,2,5] की तरह है, फिर बिमल 6 लेता है इसलिए उसका स्कोर 4+2+5 = 11, अब सरणी [4,2,5] है। फिर अमल 4 हटाता है, इसलिए उसका स्कोर 17+2+5 = 24, पत्थर सरणी [2,5] बॉब 2 हटाता है, इसलिए उसका स्कोर 11+5 = 16, वर्तमान पत्थर सरणी [5] और अमल अंतिम पत्थर को 5 मान के साथ हटाता है और 0 स्कोर प्राप्त करता है, इसलिए उसका अंतिम स्कोर 24 + 0 = 24। इसलिए उनके स्कोर का अंतर 24-16 = 8 है।

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

n := stones का आकार
dp := n आकार की एक सरणी जिसे 0 से भरा गया हो
i को n - 1 से 0 तक, 1 से घटाकर, करें
- v := stones[i]
- run_sum := 0
- j को i + 1 से n - 1 तक के लिए, करें
  - new_run := run_sum + stones[j]
  - dp[j] := (new_run - dp[j]) और (run_sum+v - dp[j-1]) का अधिकतम
  - run_sum := new_run
dp[n-1] वापस करें

उदाहरण

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

def solve(stones):
    n = len(stones)
    dp = [0] * n
    for i in range(n - 1, -1, -1):
        v = stones[i]
        run_sum = 0
        for j in range(i + 1, n):
            new_run = run_sum + stones[j]
            dp[j] = max(new_run - dp[j], run_sum + v - dp[j - 1])
            run_sum = new_run
    return dp[n - 1]

stones = [6,4,2,5,3]
print(solve(stones))

इनपुट

[6,4,2,5,3]