สมมติว่าเรามีอาร์เรย์ชื่อ stones โดย stones[i] แทนค่าของหินลำดับที่ i จากซ้าย สองเพื่อน Amal และ Bimal เล่นเกมแบบเทิร์นกับหินเหล่านี้ และ Amal เริ่มก่อนเสมอ มี n หินจัดเรียงในแถว แต่ละผู้เล่นสามารถเอาหินที่อยู่ซ้ายสุดหรือขวาสุดออกจากแถวและได้คะแนนเท่ากับผลรวมของค่าหินที่เหลืออยู่ในแถว ใครได้คะแนนสูงกว่าจะชนะ ตอนนี้ Bimal พบว่าเขาจะแพ้เสมอ จึงตัดสินใจลดความต่างของคะแนน Amal ต้องการเพิ่มความต่างของคะแนน เราต้องหาความต่างของคะแนน Amal และ Bimal หากทั้งคู่เล่นอย่างเหมาะสมที่สุด
เช่น ถ้าอินพุตคือ stones = [6,4,2,5,3] ผลลัพธ์จะเป็น 8 (ในคำอธิบายเดิมคือ 6 แต่ตัวอย่างคำนวณได้ 8) เพราะ Amal สามารถเอา 3 ได้ คะแนนเขาคือ 6+4+2+5 = 17, Bimal 0 จนถึงตอนนี้ อาร์เรย์เหลือ [6,4,2,5] Bimal เอา 6 คะแนนเขา 4+2+5 = 11 ตอนนี้อาร์เรย์ [4,2,5] Amal เอา 4 คะแนนเขา 17+2+5 = 24 อาร์เรย์ [2,5] Bimal เอา 2 คะแนนเขา 11+5 = 16 อาร์เรย์ [5] Amal เอาหินสุดท้ายค่า 5 ได้ 0 คะแนน คะแนนสุดท้ายเขา 24 + 0 = 24 ความต่างคะแนนคือ 24-16 = 8
วิธีแก้ปัญหา
- n := ขนาดของ stones
- dp := อาร์เรย์ขนาด n เติม 0
- สำหรับ i ในช่วง n - 1 ถึง 0 ลดทีละ 1:
- v := stones[i]
- run_sum := 0
- สำหรับ j ในช่วง i + 1 ถึง n - 1:
- new_run := run_sum + stones[j]
- dp[j] := max(new_run - dp[j], run_sum+v - dp[j - 1])
- run_sum := new_run
- return dp[n - 1]
ตัวอย่าง
def solve(stones):
n = len(stones)
dp = [0] * n
for i in range(n - 1, -1, -1):
v = stones[i]
run_sum = 0
for j in range(i + 1, n):
new_run = run_sum + stones[j]
dp[j] = max(new_run - dp[j], run_sum + v - dp[j - 1])
run_sum = new_run
return dp[n - 1]
stones = [6,4,2,5,3]
print(solve(stones))
อินพุต
[6,4,2,5,3]
เอาต์พุต
8
