โปรแกรมเช็คว่าผู้เล่นคนแรกหยีบลูกอมได้มากกว่าคนที่สองหรือไม่ใน Python

คำอธิบายโจทย์

เกม 2 คน ลูกอมใน list nums สลับกันหยิบจากหน้าหรือหลัง คนแรกเริ่มก่อน หาความได้เปรียบสูงสุด (score1 - score2) เช็คว่า > 0 หรือไม่

ตัวอย่าง

candies = [1, 4, 3, 8] → True (คนแรกหยิบ 8 แล้วไม่ว่าคนที่ 2 จะหยิบ 1 หรือ 3 คนแรกก็ชนะ)

วิธีแก้ปัญหา

Recursive DP (Minimax):

1. difference(left, right) = คะแนนสูงสุดที่ผู้เล่นปัจจุบันทำได้มากกว่าคู่แข่ง จากช่วง [left, right]
2. เลือกซ้าย: candies[left] - difference(left+1, right)
3. เลือกขวา: candies[right] - difference(left, right-1)
4. Base case: left == right → candies[left]
5. คนแรกชนะได้ถ้า difference(0, n-1) > 0

โค้ด Python

class Solution:
    def solve(self, candies):
        N = len(candies)
        from functools import lru_cache
        
        @lru_cache(None)
        def difference(left, right):
            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