ドットゲームとダイナミックプログラミング

Question

ダイナミックプログラミングでドットゲームのバリアントを解決しようとしています。

通常のドットゲームは、ドットのラインで再生されます。各プレイヤーは、それぞれのラインの端で1つまたは2つのドットを取り、勝つためにドットがなくなった人。

このバージョンのゲームでは、各ドットには異なる値があります。各プレイヤーは代替ターンを行い、ラインの両端にどちらかドットを取ります。ダイナミックプログラミングを使用して、最初のプレーヤーが勝つことが保証されている最大額を見つける方法を考え出したいと思います。

私はこの周りで頭を把握し、解決策の再発を書き込もうとする問題を抱えています。どんな助けも感謝しています、ありがとう！

Answer 1

このサイトを見てください： http://people.csail.mit.edu/bdean/6.046/dp/, 、特に問題10：

ゲームに最適な戦略。値v（1）... v（n）のnコインの列を考えてみましょう。交互のターンで対戦相手に対してゲームをプレイします。各ターンで、プレーヤーは行から最初または最後のコインのいずれかを選択し、列から永久に削除し、コインの値を受け取ります。最初に移動した場合、間違いなく勝つことができる最大の資金を決定します。

私があなたの投稿を正しく読んでいる場合、それはまさにあなたが望むものです。解決策は非常にシンプルで、私の意見では非常によく説明されています。