পাইথনে ইট অপসারণ গেমের সর্বাধিক স্কোর খুঁজে পাওয়ার প্রোগ্রাম

ধরুন অমল আর বিমল একটা খেলা খেলছে। তাদের একটি অ্যারে সংখ্যা রয়েছে যা এন ইট নির্ধারণ করে যার উপরে সংখ্যাযুক্ত। এই গেমটিতে, খেলোয়াড়রা বিকল্পভাবে উপরে থেকে একটি, দুই বা তিনটি ইট সরাতে পারে এবং সরানো ইটের উপর চিহ্নিত সংখ্যাগুলি সেই খেলোয়াড়ের স্কোরে যোগ করা হয়। যদি সর্বদা অমল প্রথমে শুরু করে, আমাদের খুঁজে বের করতে হবে কত স্কোর আমাল সর্বোচ্চ সুরক্ষিত হবে।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[1,2,3,4,5], তাহলে আউটপুট হবে 6 কারণ, Amal ইট {1}, {1,2} বা {1,2,3} সরাতে পারে , যদি অমল প্রথম দুই বা তিনটি উপাদান নির্বাচন করে, তাহলে বিমল সবগুলো নিতে পারে এবং সর্বোচ্চ স্কোর পেতে পারে, কিন্তু অমল প্রথমে 1 নির্বাচন করলে, বিমল সর্বাধিক {2,3,4} =9 নিতে পারে এবং অমল 5 নিতে পারে, তাই মোট আমালের স্কোর হল 1+5 =6।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

INF :=9999
n :=সংখ্যার আকার
তালিকা সংখ্যা বিপরীত করুন
temp :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
মোট :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
প্রতিটি সূচক i, এবং মান val এর জন্য, করুন
- মোট[i] :=মোট[i-1] + ভ্যাল
তাপ[0] :=সংখ্যা[0]
temp[1] :=temp[0]+সংখ্যা[1]
temp[2] :=temp[1]+সংখ্যা[2]
3 থেকে n - 1 রেঞ্জের জন্য,
- a :=সংখ্যা[i]
- b :=সংখ্যা[i] + সংখ্যা[i-1]
- c :=সংখ্যা[i] + সংখ্যা[i-1] + সংখ্যা[i-2]
- temp[i] :=সর্বোচ্চ a, b, c
রিটার্ন টেম্প[n-1]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

INF = 99999
def solve(nums):
   n = len(nums)
   nums.reverse()
   temp = [0]*n
   total = [0]*n
   for i, val in enumerate(nums):
      total[i] = total[i-1] + val
   temp[0] = nums[0]
   temp[1] = temp[0]+nums[1]
   temp[2] = temp[1]+nums[2]
   for i in range(3, n):
      a = nums[i]
      b = nums[i] + nums[i-1]
      c = nums[i] + nums[i-1] + nums[i-2]
      temp[i] = max(a, b, c)
   return temp[n-1]

nums = [1,2,3,4,5]
print(solve(nums))

ইনপুট

[1,2,3,4,5]