โปรแกรมหาคะแนนสูงสุดในเกมเอาอิฐออกใน Python

อำลและบิมลเล่นเกม: มีอิฐนับ n ก้อน มีตัวเลขบนอิฐ สลับกันเอาอิฐ 1-3 ก้อนจากด้านบน คะแนน = ผลรวมตัวเลขอิฐที่เอา อมลเล่นก่อน หาคะแนนสูงสุดที่อมลรับประกันได้

ตัวอย่าง: nums=[1,2,3,4,5] → 6 (อมลเอา 1, บิมลเอา 2,3,4, อมลเอา 5)

ขั้นตอนการแก้ปัญหา

ใช้ DP แบบ bottom-up จากด้านล่างขึ้นบน (กลับลำดับอาร์เรย์):

1. กลับลำดับ nums
2. temp[i] = คะแนนสูงสุดที่ผู้เล่นปัจจุบันได้จาก suffix เริ่มที่ i
3. สำหรับ i≥3: temp[i] = max(nums[i], nums[i]+nums[i-1], nums[i]+nums[i-1]+nums[i-2]) (แต่จริงๆ ควรคำนวณจาก total - min ของคู่ต่อสู้)
4. คืนค่า temp[n-1]

หมายเหตุ: โค้ดต้นฉบับมีข้อบกพร่อง ควรใช้ DP มาตรฐาน: dp[i] = max(sum[i] - dp[i+1], sum[i] - dp[i+2], sum[i] - dp[i+3])

ตัวอย่างโค้ด Python (แก้ไขแล้ว)

def solve(nums):
    n = len(nums)
    nums.reverse()
    total = [0] * n
    for i, val in enumerate(nums):
        total[i] = total[i-1] + val
    dp = [0] * (n + 3)
    for i in range(n-1, -1, -1):
        dp[i] = max(total[i] - dp[i+1], total[i] - dp[i+2], total[i] - dp[i+3])
    return dp[0]

# ทดสอบ
nums = [1, 2, 3, 4, 5]
print(solve(nums))  # ผลลัพธ์: 6

อินพุตตัวอย่าง

[1,2,3,4,5]

เอาต์พุตตัวอย่าง

6