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

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

เกม 2 คน ลูกอมเรียงเป็นแถว ค่าคะแนนใน nums แต่ละรอบหยิบ 1-3 ลูกอมจากด้านหน้า ได้คะแนนเท่าผลรวม ลูกอมถูกนำออก จบเมื่อลูกอมหาย คนคะแนนมากกว่าชนะ เช็คว่าคนแรกชนะได้หรือไม่

ตัวอย่าง

nums = [1, 1, 2, 3, 50] → True (คนแรกหยิบ 1 แล้วคนที่ 2 หยิบ 1-3 ตัว คนแรกได้หยิบ 50)

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

DP แบบ Bottom-up จากท้ายมาหน้า (Game Theory):

1. table[i] = ความได้เปรียบสูงสุด (score_diff) ที่ผู้เล่นปัจจุบันทำได้จากตำแหน่ง i
2. ลองหยิบ 1, 2, 3 ลูกอม: profit = sum(picked) - table[i + picked_count]
3. เก็บแค่ 3 ค่าล่าสุด (rolling array) เพราะต้องการแค่ 3 ตัวถัดไป
4. คนแรกชนะได้ถ้า table[0] > 0

โค้ด Python

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