ストーンゲームⅡ

1140。ストーンゲーム II

難易度: 中

トピック: 配列、数学、動的計画法、接頭辞の合計、ゲーム理論

アリスとボブは石の山でゲームを続けます。 一列に配置された多数の杭があり、各杭には正の整数の石の山[i]があります。 ゲームの目的は、より多くの石を獲得して終了することです。

アリスとボブは交代で、アリスが最初に始めます。 初期状態では、M = 1.

各プレイヤーのターンで、そのプレイヤーは 最初 個の残りの X 山にある すべての石 を獲得できます (1

すべての石が取られるまでゲームは続きます。

アリスとボブが最適にプレイすると仮定して、アリスが獲得できる石の最大数を返します。

例 1:

• 入力: パイル = [2,7,9,4,4]
• 出力: 10
• 説明: アリスが最初に 1 つの山を取り、ボブが 2 つの山を取り、次にアリスが再び 2 つの山を取ります。アリスは合計 2 + 4 + 4 = 10 個の山を獲得できます。アリスが最初に 2 つの山を取った場合、ボブは残りの 3 つの山をすべて取ることができます。この場合、アリスは合計 2 + 7 = 9 個の山を獲得します。したがって、10 の方が大きいため、10 を返します。

例 2:

• 入力: パイル = [1,2,3,4,5,100]
• 出力: 104

制約:

• 1
• 1 4

ヒント:

1. 動的計画法を使用します。状態は、piles[i:] と与えられた m の答えの (i, m) です。

解決策:

両方のプレイヤーが最適にプレイした場合にアリスが獲得できる石の最大数を見つけるには、動的プログラミングを使用する必要があります。ソリューションを開発するための段階的なアプローチは次のとおりです:

1. 状態と遷移を定義します:

   • dp[i][m] が最大ピック制限 m で山 i から始めてアリスが収集できる最大の石を表す 2D DP 配列を定義します。
   • プレフィックス合計配列を使用して、部分配列内の石の合計を効率的に計算します。

2. 基本ケース:

   • 選択できる石が残っていない場合、スコアは 0 です。

3. 再帰的なケース:

   • 各山 i と最大許容ピック m について、すべての可能な動きを考慮してアリスが収集できる石の最大数を計算します (1 ～ 2 メートルの山を取る)。

4. 遷移関数:

   • アリスが選択できる山のそれぞれの可能な数について、アリスが取得できる石の合計を計算し、将来の状態の結果を使用して最適な手を決定します。

このソリューションを PHP で実装してみましょう: 1140。ストーンゲーム II

<?php
// Example usage
$solution = new Solution();
$piles1 = [2, 7, 9, 4, 4];
$piles2 = [1, 2, 3, 4, 5, 100];
echo $solution->stoneGameII($piles1) . "\n"; // Output: 10
echo $solution->stoneGameII($piles2) . "\n"; // Output: 104
?>

説明：

1. プレフィックス合計計算: これは、任意の山 i から j までの石の合計を素早く計算するのに役立ちます。
2. DP 配列の初期化: dp[i][m] は、アリスが山 i から開始して最大ピック制限 m で取得できる最大の石を保持します。
3. 動的プログラミング遷移: 各山と m について、アリスが取得できる可能な山の数を反復し、それに応じて DP 配列を更新することで、アリスが収集できる石の最大数を計算します。

このアプローチにより、動的プログラミングを利用して冗長な計算を回避し、解が効率的に計算されます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がストーンゲームⅡの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。