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

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

इसलिए, यदि इनपुट पत्थरों की तरह है =[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 :=पत्थरों का आकार
dp :=आकार n की एक सरणी और 0 से भरें
मैं के लिए n - 1 से 0 की श्रेणी में, 1 से घटाएं
- v :=पत्थर[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
रिटर्न डीपी[एन -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]