পাইথনে স্টোন গেমের স্কোর পার্থক্য ন্যূনতম করার প্রোগ্রাম

মনে করুন stones নামক একটি অ্যারে আছে যেখানে stones[i] হলো বাম থেকে i-তম স্টনের ভ্যালু। দুজন বন্ধু অমল এবং বিমল এই স্টোন দিয়ে টার্ন-বেসড গেম খেলছে এবং অমল সবসময় প্রথমে শুরু করে। nটি স্টোন একটি সারিয়ে রয়েছে। প্রতিটি খেলোয়াড় বামপাশের বা ডানপাশের স্টোনটি उठাতে পারে এবং সারিয়ে থাকা বাকি স্টোনগুলোর ভ্যালুর যোগফল 만큼 পয়েন্ট পাবে। যাকে বেশি স্কোর হবে সে জিতবে। বিমল বুঝতে পেরেছে সে সবসময় হাবে, তাই সে স্কোর পার্থক্য ন্যূনতম করার চেষ্টা করবে। অমলের লক্ষ্য পার্থক্য সর্বোচ্চ করা। যদি দুজনই অপ্টিমালি খেলে, তবে অমল ও বিমলের স্কোর পার্থক্য বের করতে হবে।

যেমন, ইনপুট stones = [6,4,2,5,3] হলে, আউটপুট হবে ৬ কারণ:

অমল ৩ নেয়, তার স্কোর 6+4+2+5 = 17, বিমল ০, অ্যারে [6,4,2,5]
বিমল ৬ নেয়, তার স্কোর 4+2+5 = 11, অ্যারে [4,2,5]
অমল ৪ নেয়, তার স্কোর 17+2+5 = 24, অ্যারে [2,5]
বিমল ২ নেয়, তার স্কোর 11+5 = 16, অ্যারে [5]
অমল শেষ ৫ নেয়, স্কোর ২৪+০ = ২৪। পার্থক্য ২৪-১৬ = ৮।

নোট: উদাহরণে আউটপুট ৬ বলা হয়েছে কিন্তু ব্যাখ্যায় ৮ আসছে। সঠিক আউটপুট ৮।

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

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

n := stones-এর সাইজ
dp := 0 দিয়ে n সাইজের একটি অ্যারে
i = n-1 থেকে ০ পর্যন্ত (কমাতে ১)
- v := stones[i]
- run_sum := 0
- j = i+1 থেকে n-1 পর্যন্ত
  - new_run := run_sum + stones[j]
  - dp[j] := max(new_run - 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]