পাইথনে স্টোন গেমে সর্বোচ্চ স্কোর বের করার প্রোগ্রাম

মনে করুন একটি সারিয়ে অনেকগুলো স্টোন আছে এবং প্রতিটি স্টোর একটি সংশ্লিষ্ট নম্বর আছে যা stoneValue অ্যারেতে দেওয়া আছে। প্রতিটি রাউন্ডে অমল সারিয়ের দুটি অংশে ভাগ করে, তারপর বিমল প্রতিটি অংশের ভ্যালু হিসাব করে (অংশে থাকা সব স্টোর ভ্যালুর যোগফল)। বিমল যে অংশটির ভ্যালু বেশি সেটাকে ফেলে দেয়, এবং অমলের স্কোর বাকি অংশটির ভ্যালু 만큼 বড়ে। দুটি অংশের ভ্যালু সমান হলে বিমল অমলকে ডিসাইড করতে দেয় কোটি অংশ ফেলবে। পরের রাউন্ড বাকি অংশটি দিয়ে শুরু হয়। গেম শেষ হয় যখন একটাই স্টোন বাকি থাকে। অমল যা সর্বোচ্চ স্কোর পেতে পারে তা বের করতে হবে।

যেমন, ইনপুট stoneValue = [7,3,4,5,6,6] হলে, আউটপুট হবে:

রাউন্ড ১: অমল ভাগ করে [7,3,4], [5,6,6]। বাম যোগফল ১৪, ডান ১৭। বিমল ডান ফেলে, অমলের স্কোর ১৪।
রাউন্ড ২: অমল ভাগ করে [7], [3,4]। বিমল বাম ফেলে, অমলের স্কোর (১৪ + ৭) = ২১।
রাউন্ড ৩: অমল শুধু [3], [4] ভাগ করতে পারে। বিমল ডান ফেলে, অমলের স্কোর (২১ + ৩) = ২৪।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

dfs() ফাংশন ডিফাইন করুন। এটি start, end প্যারামিটার নেবে
যদি start >= end হয়, তবে
- 0 রিটার্ন করুন
max_score := 0
cut = start থেকে end-১ পর্যন্ত
- sum1 := partial_sum[start, cut]
- sum2 := partial_sum[cut+1, end]
- যদি sum1 > sum2 হয়, তবে
  - score := sum2 + dfs(cut+1, end)
- অন্যথায় যদি sum1 < sum2 হয়, তবে
  - score := sum1 + dfs(start, cut)
- অন্যথায়,
  - score := sum1 + max(dfs(start, cut), dfs(cut+1, end))
- max_score := max(score, max_score)
max_score রিটার্ন করুন
getPartialSum() ফাংশন ডিফাইন করুন।
i = 0 থেকে n-1 পর্যন্ত
- partial_sum[i, i] := stoneValue[i]
i = 0 থেকে n-1 পর্যন্ত
- j = i+1 থেকে n-1 পর্যন্ত
  - partial_sum[i, j] := partial_sum[i, j-1] + stoneValue[j]
মেইন মেথড থেকে:
n := stoneValue-এর সাইজ
partial_sum := 0 দিয়ে n x n স্কোয়ার অ্যারে
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]