পাইথনে ক্যান্ডি রেসে প্রথম খেলোয়াড় বেশি ক্যান্ডি নিতে পারে কিনা চেক করা

দুই খেলোয়াড় একটি লিস্ট candies-এর দুটি ছোর থেকে ক্যান্ডি নিচ্ছে। খেলোয়াড় ১ প্রথমে খেলে। প্রতিটি টার্নে তিনি সামনের বা পিছনের ক্যান্ডি নিতে পারেন। খেলোয়াড় ১ কি খেলোয়াড় ২-র চেয়ে বেশি ক্যান্ডি নিতে পারবে তা বের করতে হবে।

উদাহরণ: candies = [1, 4, 3, 8] → আউটপুট True। কারণ খেলোয়াড় ১ প্রথমে ৮ নিলে বাকি যেকোনো পক্ষ থেকে খেলোয়াড় ২ নিলে খেলোয়াড় ১ বাকিটা নিয়ে জিতে পারবে।

সমাধানের ধাপসমূহ (রিকার্সিভ DP / Minimax)

1. N := len(candies)

2. difference(left, right) ফাংশন ডিফাইন করুন:

   • যদি left == right, তবে candies[left] রিটার্ন করুন।

   • রিটার্ন max(candies[left] - difference(left+1, right), candies[right] - difference(left, right-1))

3. মেইন থেকে difference(0, N-1) > 0 চেক করুন।

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

class Solution:
    def solve(self, candies):
        N = len(candies)
        def difference(left, right):
            nonlocal candies
            if left == right:
                return candies[left]
            return max(candies[left] - difference(left + 1, right),
                       candies[right] - difference(left, right - 1))
        return difference(0, N - 1) > 0

ob = Solution()
candies = [1, 4, 3, 8]
print(ob.solve(candies))

ইনপুট

[1, 4, 3, 8]

আউটপুট

True