Pythonでストーンゲームのスコアの最小差を見つけるプログラム

stones[i]が左からi番目の石の値を表すstonesという配列があるとします。 2人の友人のAmalとBimalがこれらの石を使ってターン制のゲームを再プレイし、Amalが常に最初に開始します。 n個の石が一列に並んでいます。各プレイヤーは、列から左端の石または右端の石のいずれかを削除し、列の残りの石の値の合計に等しいポイントを取得できます。より高いスコアを獲得する人が勝ちます。さて、Bimalは常にこのゲームに負けることを発見したので、スコアの差を最小限に抑えることにしました。アマルの目標は、スコアの差を最大化することです。したがって、AmalとBimalの両方が最適に再生される場合、それらのスコアの違いを見つける必要があります。

したがって、入力がstones =[6,4,2,5,3]の場合、Amalは3を取ることができるため、出力は6になります。したがって、彼のスコアは6 + 4 + 2 + 5 =17、Bimalのスコアになります。これまでのところ0であり、配列は[6,4,2,5]のようです。次に、Bimalは6を取るので、スコア4 + 2 + 5 =11になり、配列は[4,2,5]になります。次に、アマルは4を削除し、スコア17 + 2 + 5 =24、石の配列[2,5]ボブは2を削除し、スコア11 + 5 =16、現在の石の配列[5]、アマルは値5の最後の石を削除します。スコアが0になったので、彼の最終スコアは24 + 0 =24です。したがって、スコアの差は24-16=8です。

これを解決するには、次の手順に従います-

• n：=石のサイズ
• dp：=サイズnの配列で、0で埋めます
• n-1から0の範囲のiの場合、1ずつ減らします。
  • v：=石[i]
  • run_sum：=0
  • i +1からn-1の範囲のjの場合、do
    • new_run：=run_sum + stones [j]
    • dp [j]：=（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