Pythonのゲームで収集可能な最大ポイントを見つけるためのプログラム

カードゲームをしているとしましょう。それぞれに番号が付いた直線状に配置されたいくつかのカードが与えられます。カードの番号はランダムに配布されます。カードの最初と最後に、番号1が付いた2枚のカードが挿入されます。さて、ゲームでは、与えられたカードを手に取って最大ポイントを集める必要があります。カードは配列「カード」で表され、配列内の要素はカードの数を表します[i]。カードiを受け取ると、ポイントカード[i-1]*カード[i]*カード[i+1]を集めます。カードを手に取ると、cards[i-1]とcards[i]が隣人になります。したがって、これらの与えられたカードから、私たちが集めることができる最大のポイントを見つけます。

したがって、入力がcards =[7、5、9、10]の場合、出力は1025

したがって、ゲームでは、ピックアップすることができます-

インデックス1のカードで、7 * 5 * 9=315ポイントを獲得します。

新しいインデックス1のカードで、7 * 9 * 10=630ポイントを獲得します。

インデックス1のカードで、7 * 10=70ポイントを獲得します。

最後のカードで10ポイント獲得。

合計ポイント=315+ 630 + 70 + 10 =1025

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

• 関数search（）を定義します。これにはx、y
  がかかります
  • temp：=0
  • x + 1からyの範囲のzについては、
    • temp：=最大（temp、search（x、z）+ search（z、y）+カード[x]*カード[z]*カード[y]）
  • リターン温度
• リストカードの最初と最後にそれぞれ値1と1を挿入します
• return search（0、カードのサイズ-1）

例

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

def solve(cards):
   def search(x, y):
      temp = 0
      for z in range(x + 1, y):
         temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
      return temp
   cards = [1] + cards + [1]
   return search(0, len(cards) - 1)

print(solve([7, 5, 9, 10]))

入力

[7, 5, 9, 10]

出力

1025