HackerRankの "Bricks Game"

Question

私はHackerRankのDynamic Programmingセクションからthisの問題を解決しようとしていました。私は編集の解説を読んで理解しています。しかし、それはダイナミックプログラミングのアプローチに直接ジャンプします。私はブルートフォースのアプローチがこの問題のために何であるかを知りたい。

説明：あなたとあなたの友人が、N個のレンガからなるスタックを使用してゲームをプレイすることを決定しました。このゲームでは、代わりに1,2,3のレンガを上から削除し、削除されたレンガ上でエッチングされた数字があなたのスコアに追加されます。可能な限り最大のスコアを得るためにプレーする必要があります。あなたの友人も最適にプレイし、あなたは最初の動きをします。

私の最初の考えは、1,2,3の長さの可能なすべての組合せの組み合わせを、スタックの上端から下端まで列挙することです。この列挙体をSと呼ぶことにしましょう。次に、S内のすべてのx（あなたの得点）とy（相手の得点）のすべての（x、y）を見つけます。ここでx！= yです。最後に、すべてのペアを繰り返して、最大得点（たとえば、xの最大合計）を計算します。

Answer 1

ここでは、動的プログラミングは、同じサブ問題を何回も計算することを避けるための単なる方法です（他の可能性はmemoizationを使用することです）。

問題のこれらの種類にアプローチするための一般的な考え方は以下の通りです：

AとBは最初の選手とA動くとします。さらに、f(n,p)は、nのスタックを持つプレーヤーpの最大スコアを示します。つまり、nのpのスタックがオンになっています。

アイデアは非常に簡単で、Aは最大化したいと考えていますf(n,A)。 Aスコア場合2個のレンガ

を取る

• 1つのブリック
• をとり、また3個のレンガ

を取る：最大で3つの異なる移動を行うことができ、入力で与えられた初期位置からAでいることに注意してくださいX、次にBスコアS(n) - X、ここでS(n)は、nボトムレンガの得点の合計です。

これらの観察に基づいて、我々はそれを書くことができます：

f(n,A) = max(S(n)-f(n-1,B), S(n)-f(n-2,B), S(n)-f(n-3,B))。

つまり、彼の最善の結果はこれらの利用可能な動きから最大です（スタックが小さい場合、3つ以下の動きが利用可能であることに注意してください）。

は今、ダイナミックプログラミングはちょうどf(n,p)何度も同じ値を計算避けるために使用されている - あなたはf(n,A)ための式を展開すると、あなたはnが成長するとき、彼らはそこに、より多くのを発生する可能性があることがわかります。したがって、解を最適化するために、すでに計算されたfの値がメモリに保存され、必要に応じて一定時間内に返されます。

Answer 2

Minimax algorithmをご覧ください。あなたが一般的に完全なツリーを構築して、あるレベルがあなたのすべての可能な移動を生成し、次のレベルは、あなたが前のレベルであなたが生成したすべての州のために、対戦相手のすべての可能な移動を生成し続けます。各レベルでは、次のレベルの最悪のシナリオでの損失を最小限に抑える必要があります。ここではすべての可能な移動/分岐が生成されているので、かなり多くのブルートフォースです。

明らかに、Minimaxツリーでプルーニングを適用できますが、最初にブルートフォース方式を検討する必要があります。