โปรแกรมค้นหาความแตกต่างขั้นต่ำของคะแนนเกมสโตนใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า stone โดยที่ stones[i] แทนค่าของ ith stone จากด้านซ้าย เพื่อนสองคน Amal และ Bimal กำลังเล่นเกมผลัดกันเล่นด้วยก้อนหินเหล่านี้และ Amal จะเริ่มก่อนเสมอ มีหิน n ก้อนเรียงกันเป็นแถว ผู้เล่นแต่ละคนสามารถเอาหินซ้ายสุดหรือหินขวาสุดออกจากแถว และรับคะแนนเท่ากับผลรวมของค่าของหินที่เหลืออยู่ในแถว ใครจะได้คะแนนสูงกว่าจะเป็นผู้ชนะ ตอนนี้ Bimal พบว่าเขาจะแพ้เกมนี้เสมอ ดังนั้นเขาจึงตัดสินใจลดความแตกต่างของคะแนนให้เหลือน้อยที่สุด เป้าหมายของ Amal คือการเพิ่มความแตกต่างของคะแนนให้ได้มากที่สุด เราจึงต้องค้นหาความแตกต่างในคะแนนของ Amal และ Bimal หากทั้งคู่เล่นได้ดีที่สุด

ดังนั้นหากอินพุตเป็นเหมือนก้อนหิน =[6,4,2,5,3] ผลลัพธ์จะเป็น 6 เพราะ 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] Bob ลบ 2 ดังนั้นคะแนนของเขา 11+5 =16, แถวหินปัจจุบัน [5] และ Amal ลบหินก้อนสุดท้ายที่มีค่า 5 และได้ 0 คะแนน ดังนั้นคะแนนสุดท้ายของเขาคือ 24 + 0 =24 ดังนั้นผลต่างของคะแนนคือ 24-16 =8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n :=ขนาดของหิน
dp :=อาร์เรย์ขนาด n และเติม 0
สำหรับฉันในช่วง n - 1 ถึง 0, ลดลง 1 ทำ
- v :=หิน[i]
- run_sum :=0
- สำหรับ j ในช่วง i + 1 ถึง n - 1 ทำ
  - new_run :=run_sum + stones[j]
  - dp[j] :=(สูงสุดของ new_run - dp[j]) และ (run_sum+v - dp[j - 1])
  - run_sum :=new_run
ส่งคืน 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]