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

いくつかの石が一列に配置されており、これらの石のそれぞれに、配列stoneValueで指定された関連付けられた番号があるとします。各ラウンドで、Amalは行を2つの部分に分割し、Bimalは各部分の値を計算します。これは、この部分のすべての石の値の合計です。 Bimalは最大値の部分を破棄し、Amalのスコアは残りの部分の値だけ増加します。 2つの部分の値が同じである場合、BimalはAmalにどちらの部分を破棄するかを決定させます。次のラウンドは残りの部分から始まります。石が1つだけ残っていると、ゲームは終了します。アマルが得ることができる最大のスコアを見つける必要があります。

したがって、入力がstoneValue =[7,3,4,5,6,6]の場合、出力は

• ラウンド1で、Amalは[7,3,4]、[5,6,6]のように行を分割します。左の行の合計は14、右の行の合計は17です。Bimalは右の行を破棄し、Amalのスコアは14になりました。

• ラウンド2で、アマルは行を[7]、[3,4]に分割します。したがって、Bimalは左の行を破棄し、Amalのスコアは（14 + 7）=21になります。

• ラウンド3では、アマルは[3]、[4]の行を分割する唯一の選択肢があります。 Bimalは右の行を破棄し、Amalのスコアは（21 + 3）=24になります。

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

• 関数dfs（）を定義します。これには開始、終了が必要です

• start> =endの場合、

  • 0を返す

• max_score：=0

• 範囲内の最初から最後までのカットについては、実行してください

  • sum1：=partial_sum [start、cut]

  • sum2：=partial_sum [cut + 1、end]

  • sum1> sum2の場合、

    • スコア：=sum2 + dfs（cut + 1、end）

  • それ以外の場合、sum1

    • スコア：=sum1 + dfs（start、cut）

  • それ以外の場合

    • スコア：=sum1 + dfs（start、cut）およびdfs（cut + 1、end）の最大値

  • max_score：=スコアとmax_scoreの最大値

• max_scoreを返す

• 関数getPartialSum（）を定義します。これには時間がかかります

• 0からn-1の範囲のiの場合、実行

  • partial_sum [i、i]：=stoneValue [i]

• 0からn-1の範囲のiの場合、実行

  • i +1からn-1の範囲のjの場合、実行

    • 部分合計[i、j]：=部分合計[i、j-1] + stoneValue [j]

• メインの方法から、次のようにします

• n：=stoneValueのサイズ

• partial_sum：=サイズn x nで、0で埋められた正方形の配列

• getPartialSum（）

• dfs（0、n-1）を返す

例

理解を深めるために、次の実装を見てみましょう

def solve(stoneValue):
   def dfs(start, end):
      if start >= end:
         return 0
      max_score = 0

      for cut in range(start, end):
         sum1 = partial_sum[start][cut]
         sum2 = partial_sum[cut+1][end]
         if sum1 > sum2:
            score = sum2+dfs(cut+1, end)
         elif sum1 < sum2:
            score = sum1+dfs(start, cut)
         else:
            score = sum1+max(dfs(start, cut), dfs(cut+1, end))
            max_score = max(score, max_score)
      return max_score


   def getPartialSum():
      for i in range(n):
         partial_sum[i][i] = stoneValue[i]
      for i in range(n):
         for j in range(i+1, n):
            partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]


   n = len(stoneValue)
   partial_sum = [[0]*n for _ in range(n)]
   getPartialSum()
   return dfs(0, n-1)

stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))

入力

[7,3,4,5,6,6]

出力

0