পাইথনে ক্যান্ডি গেমে بازیکن ১ কি জিতে পারে তা চেক করা

দুই بازیکن একটি লাইন থেকে ক্যান্ডি নিচ্ছে। প্রতিটি ক্যান্ডির একটি পয়েন্ট আছে (nums লিস্ট)। প্রতিটি টার্নে একজন بازیکن সামনে থেকে ১, ২, বা ৩টি ক্যান্ডি নিতে পারে এবং তাদের পয়েন্ট যোগ করে নিতে পারে। সব ক্যান্ডি শেষ হলে যাদের পয়েন্ট বেশি সে জিতে। খেলোয়াড় ১ প্রথমে খেলে। آیا খেলোয়াড় ১ জিতে পারে কিনা বের করতে হবে।

উদাহরণ: nums = [1, 1, 2, 3, 50] → আউটপুট True। কারণ খেলোয়াড় ১ প্রথমে ১টি নিলে বাকি ১, ২, বা ৩টি নিলেও খেলোয়াড় ১ পরবর্তীতে ৫০ পাওয়া যায়।

সমাধানের ধাপসমূহ (DP)

1. n := len(nums), table := [0, 0, 0] (স্লাইডিং উইন্ডো DP)।

2. i = n-1 থেকে 0 পর্যন্ত লুপ:

   • profit = -inf, sum_val = 0

   • j = i থেকে min(i+3, n) পর্যন্ত:

     • sum_val += nums[j]

     • profit = max(profit, sum_val - table[j-i])

   • table = [profit, table[0], table[1]] (শিফট করুন)।

3. table[0] > 0 হলে True, অন্যথায় False রিটার্ন করুন।

পাইথন কোড উদাহরণ

import math
class Solution:
    def solve(self, nums):
        n = len(nums)
        table = [0, 0, 0]
        for i in range(n - 1, -1, -1):
            profit = -math.inf
            sum_val = 0
            for j in range(i, min(i + 3, n)):
                sum_val += nums[j]
                profit = max(profit, sum_val - table[j - i])
            table[:] = [profit, table[0], table[1]]
        return table[0] > 0

ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))

ইনপুট

[1, 1, 2, 3, 50]

আউটপুট

True