Python程式：查詢石頭遊戲得分最小差值

假設我們有一個名為stones的陣列，其中stones[i]表示從左側起第i塊石頭的值。兩位朋友Amal和Bimal正在玩一個基於回合的石頭遊戲，Amal總是先開始。有n塊石頭排成一排。每個玩家可以移除最左邊或最右邊的石頭，並獲得等於該行中剩餘石頭值總和的分數。得分較高者獲勝。現在，Bimal發現他總是會輸掉這場遊戲，所以他決定將分數差最小化。Amal的目標是最大化分數差。因此，我們必須找到如果他們都採取最佳策略，Amal和Bimal的分數差。

因此，如果輸入類似於stones = [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 := stones的大小
  • dp := 一個大小為n的陣列，並用0填充
  • 對於從n - 1到0的i，遞減1，執行以下操作：
    • v := stones[i]
    • run_sum := 0
    • 對於從i + 1到n - 1的j，執行以下操作：
      • 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]

輸出

8

更新於: 2021年10月6日

135 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告