Pythonでカードゲームの最大獲得ポイントを求めるプログラム

問題の概要

カードゲームを考えてみましょう。複数のカードが一列に並べられており、それぞれのカードには数字が書かれています。数字はランダムに配置されており、列の先頭と末尾には数字「1」が書かれたカードが挿入されています。このゲームでは、カードを1枚ずつ拾っていき、合計ポイントを最大化することが目標です。

カードは配列「cards」で表され、各要素cards[i]がそのカードに書かれた数字を表します。カードiを拾うと、cards[i - 1] × cards[i] × cards[i + 1] のポイントを獲得できます。カードを1枚取り除くたびに、その左右にあったカード同士が新しく隣接します。このルールのもとで、獲得できる最大ポイントを求めます。

具体例

例えば、入力が cards = [7, 5, 9, 10] の場合、出力は 1025 になります。以下の手順でカードを拾うと最大ポイントが得られます。

• インデックス1のカード（5）を拾う → 7 × 5 × 9 = 315ポイント
• 新しいインデックス1のカード（9）を拾う → 7 × 9 × 10 = 630ポイント
• インデックス1のカード（10）を拾う → 7 × 10 × 1 = 70ポイント
• 最後のカード（10）を拾う → 7 × 10 × 1 = 70ポイント…ではなく、残りの計算では端の「1」と掛け合わせて 10ポイント を獲得

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

解決のアプローチ

この問題は、区間を再帰的に分割して解く「区間DP（インターバル・ダイナミックプログラミング）」の考え方で効率的に解けます。ポイントとなるのは、「ある区間の中で最後に取るカードzを固定する」と、区間が左側 [x, z] と右側 [z, y] に独立して分割できるという点です。

具体的な手順は以下の通りです。

• 関数 search(x, y) を定義する。引数x, yは区間の両端のインデックスを表す
  • 変数 temp := 0 で初期化
  • z を x + 1 から y - 1 まで繰り返す
    • temp := max(temp, search(x, z) + search(z, y) + cards[x] × cards[z] × cards[y])
  • temp を返す
• リスト cards の先頭と末尾に「1」を挿入する
• search(0, len(cards) - 1) の結果を返す

実装例

それでは、Pythonでの実装を見てみましょう。

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

補足：計算量と改善のヒント

上記の素朴な再帰実装では、同じ区間を何度も計算するため、カード枚数nに対して指数時間かかる可能性があります。実用的な規模の入力に対応するには、@lru_cache デコレータや辞書を使ったメモ化を追加すると、計算量を O(n³) まで抑えられます。また、ボトムアップ方式で二次元テーブルを埋めていく実装に書き換えることで、再帰の深さ制限によるエラーも回避できます。