1140。石头游戏ii

难度：中等

主题： 数组、数学、动态规划、前缀和、博弈论

爱丽丝和鲍勃继续玩石头堆游戏。 有许多堆排成一排，每堆有正整数个石子piles[i]。 游戏的目标是以最多的石子结束。

爱丽丝和鲍勃轮流，爱丽丝先开始。 最初，m = 1.

在每个玩家的回合中，该玩家可以拿走第一个剩余 x 堆中的所有石头，其中 1

游戏继续进行，直到所有的石子都被拿走。

假设爱丽丝和鲍勃发挥最佳，返回爱丽丝可以获得的最大石头数量。

示例1：

• 输入： 桩 = [2,7,9,4,4]
• 输出： 10
• 解释： 如果 alice 一开始拿了一堆，bob 拿了两堆，然后 alice 又拿了 2 堆。爱丽丝总共可以获得 2 + 4 + 4 = 10 堆。如果爱丽丝一开始拿了两堆，那么鲍勃就可以拿走剩下的三堆。在这种情况下，爱丽丝总共得到 2 + 7 = 9 堆。所以我们返回 10，因为它更大。

示例2：

• 输入： 桩 = [1,2,3,4,5,100]
• 输出： 104

限制：

• 1
• 1 4

提示：

1. 使用动态规划：对于给定 m 的piles[i:] 的答案，状态为 (i, m)。

解决方案：

我们需要使用动态规划来找到如果双方都发挥最佳状态，alice 可以获得的最大石头数量。以下是开发解决方案的分步方法：

1. 定义状态和转换：

   • 定义一个 2d dp 数组，其中 dp[i][m] 表示 alice 从第 i 堆开始可以收集的最大石头，最大拾取限制为 m。
   • 使用前缀和数组来高效计算子数组中石头的总和。

2. 基本案例：

   • 如果没有剩下的石头可供采摘，则得分为 0。

3. 递归案例：

   • 对于每一堆 i 和最大允许拾取 m ，通过考虑所有可能的移动（取 1 到 2m 堆）来计算 alice 可以收集的最大石头。

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-&gt;stoneGameII($piles2) . "n"; // Output: 104
?&gt;

解释：

1. 前缀总和计算：这有助于快速计算任意一堆 i 到 j 中的石子的总和。
2. dp 数组初始化： dp[i][m] 保存 alice 从 i 堆开始可以获取的最大石头，最大拾取限制为 m。
3. 动态编程转换： 对于每一堆和 m，通过迭代她可以获取的可能堆数并相应更新 dp 数组来计算 alice 可以收集的最大石头。

这种方法确保了解决方案的高效计算，利用动态规划来避免冗余计算。

联系链接

如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• github