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

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

সুতরাং, ইনপুট যদি stoneValue =[7,3,4,5,6,6] এর মত হয়, তাহলে আউটপুট হবে

রাউন্ড 1 এ, অমল সারিটিকে [7,3,4], [5,6,6] ভাগ করে। বাম সারির যোগফল 14 এবং ডান সারির যোগফল 17। বিমল ডান সারিটি ফেলে দেয় এবং অমলের স্কোর এখন 14।
রাউন্ড 2 এ, আমাল সারিটিকে [7], [3,4] ভাগ করে। তাই বিমল বাম সারিটি ফেলে দেয় এবং অমলের স্কোর হয়ে যায় (14 + 7) =21৷
রাউন্ড 3 এ, সারিটি ভাগ করার জন্য অমলের একটি মাত্র পছন্দ আছে যা হল [3], [4]। বিমল ডান সারি ছুড়ে ফেলে এবং অমলের স্কোর এখন (21 + 3) =24।

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

একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি শুরু, শেষ হবে
যদি শুরু>=শেষ হয়, তাহলে
- রিটার্ন 0
সর্বোচ্চ_স্কোর :=0
পরিসীমা শুরু থেকে শেষ করার জন্য, করুন
- sum1 :=partial_sum[শুরু, কাটা]
- sum2 :=partial_sum[cut+1, end]
- যদি sum1> sum2 হয়, তাহলে
  - স্কোর :=sum2 + dfs(cut+1, end)
- অন্যথায় যখন sum1
  - স্কোর :=sum1 + dfs(শুরু, কাটা)
- অন্যথায়,
  - স্কোর :=যোগফল 1 + সর্বাধিক dfs (শুরু, কাটা) এবং dfs (কাট+1, শেষ)
- সর্বোচ্চ_স্কোর :=সর্বোচ্চ স্কোর এবং সর্বোচ্চ_স্কোর
সর্বোচ্চ_স্কোর ফেরত দিন
একটি ফাংশন সংজ্ঞায়িত করুন getPartialSum()। এটি লাগবে
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- partial_sum[i, i] :=stoneValue[i]
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- i+1 থেকে n - 1 রেঞ্জের মধ্যে j এর জন্য, করুন
  - partial_sum[i, j] :=partial_sum[i, j-1] + stoneValue[j]
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
n :=পাথরের মান
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]