0

これは、2 人のプレイヤーが次のゲームをプレイする古典的なゲームです。

異なる金種のコインが n 枚並んでいます。このゲームでは、プレーヤーは極端な左または極端な右からコインを選びます (彼らは.5 の確率で任意の極端からやみくもに選びます。どちらも愚かです)。ゲームを開始するプレーヤーの予想合計を数えたいだけです。

このために、プレイヤーが持つことができる値のすべての可能な組み合わせを合計したいと思います。すべての可能な結果値を合計する再帰的なソリューションを使用していますが、サブ問題が重複しています。私はそれを効率的にしたいと思っており、これらの重複するサブ問題をメモしたいと考えています。

それを実行するためのロジックを収集できません。誰か助けてください。

4

1 に答える 1

0

アイデアは、各行のサブインターバルが両方のプレーヤーの合計を格納することです。

間隔F(start, end)でプレーする最初のプレーヤーの可能な合計を示すとします[start, end]。同様の define S(start, end)。のように、和の確率とともに可能な和を辞書に格納でき{2: 0.25, 5: 0.25, 6: 0.5}ます。

再帰が保持するよりも：

F(start, end) = {row[end]  +sum: p/2,  for sum,p in S(start, end-1)} +
                {row[start]+sum: p/2,  for sum,p in S(start+1, end)}
S(start, end) = {sum: p/2, for sum,p in F(start, end-1)} +
                {sum: p/2, for sum,p in F(start+1, end)}
F(start, end) = {row[start]: 1} if start == end
S(start, end) = {} if start == end

これは、間隔の長さを増やすことで計算できます。

for length = 0 to row_length-1:
  for start = 1 to row_length - length:
    calculate `F(start, start+length)` and `S(start, start+length)`

辞書F(1, row_length)とS(1, row_length)は、期待される合計を計算するために使用されます。

于 2012-10-13T18:12:20.257 に答える