1140。石头游戏ii
难度：中等
主题： 数组、数学、动态规划、前缀和、博弈论
爱丽丝和鲍勃继续玩石头堆游戏。 有许多堆排成一排，每堆有正整数个石子piles[i]。 游戏的目标是以最多的石子结束。
爱丽丝和鲍勃轮流，爱丽丝先开始。 最初，m = 1.
在每个玩家的回合中，该玩家可以拿走第一个剩余 x 堆中的所有石头，其中 1 <= x <= 2m。 然后，我们设置 m = max(m, x).
游戏继续进行，直到所有的石子都被拿走。
假设爱丽丝和鲍勃发挥最佳，返回爱丽丝可以获得的最大石头数量。
示例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 <= 桩.长度 <= 100
- 1 <= 一堆[i] <= 104
提示：
- 使用动态规划：对于给定 m 的piles[i:] 的答案，状态为 (i, m)。
解决方案：
我们需要使用动态规划来找到如果双方都发挥最佳状态，alice 可以获得的最大石头数量。以下是开发解决方案的分步方法：
-
定义状态和转换：
- 定义一个 2d dp 数组，其中 dp[i][m] 表示 alice 从第 i 堆开始可以收集的最大石头，最大拾取限制为 m。
- 使用前缀和数组来高效计算子数组中石头的总和。
-
基本案例：
- 如果没有剩下的石头可供采摘，则得分为 0。
-
递归案例：
- 对于每一堆 i 和最大允许拾取 m ，通过考虑所有可能的移动（取 1 到 2m 堆）来计算 alice 可以收集的最大石头。
-
转换函数：
- 对于爱丽丝可以挑选的每种可能的堆数，计算爱丽丝可以获得的石头总数，并使用未来状态的结果来决定最佳移动。
让我们用 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 ?>
解释：
- 前缀总和计算：这有助于快速计算任意一堆 i 到 j 中的石子的总和。
- dp 数组初始化： dp[i][m] 保存 alice 从 i 堆开始可以获取的最大石头，最大拾取限制为 m。
- 动态编程转换： 对于每一堆和 m，通过迭代她可以获取的可能堆数并相应更新 dp 数组来计算 alice 可以收集的最大石头。
这种方法确保了解决方案的高效计算，利用动态规划来避免冗余计算。
联系链接
如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
- 领英
- github
