পাইথনে স্টোন গেম স্কোরের ন্যূনতম পার্থক্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের স্টোন নামক একটি অ্যারে আছে যেখানে পাথর [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 রেঞ্জের i এর জন্য, 1 কমিয়ে
- v :=পাথর[i]
- run_sum :=0
- করুন
  - new_run :=run_sum + stones[j]
  - dp[j] :=(সর্বাধিক নতুন_রান - 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]