C++ 石头游戏

在本文中，我们将讨论 C++ 中的石子游戏。

问题陈述

鲍勃和爱丽丝玩石子堆游戏。每堆石子都包含正整数数量的石子，并且有偶数堆石子排成一排。游戏的目标是最终获得最多数量的石子。所有石子堆中的石子数量都是奇数，因此不会出现平局。爱丽丝先手，鲍勃紧随其后。玩家在每回合可以选择从行首或行尾取走整堆石子。当没有石子堆可取时，拥有最多石子的玩家获胜。

如果爱丽丝和鲍勃都发挥最佳水平，如果爱丽丝获胜则返回 true，如果鲍勃获胜则返回 false。

假设石子堆排成一排如下：

示例 1

石子堆：{5, 3, 4, 5}

玩家 A

• A 将开始游戏。
• 他们可以选择堆 1 或堆 4。
• 如果 A 选择堆 1
  
  • 石子数 = 5。

玩家 B

• 如果 A 选择堆 1，B 的选择是堆 2 或堆 4。
• 如果 B 选择堆 2
  • 石子数 = 3。
  • 否则，如果 B 选择堆 4，石子数 = 5。
• 如果 B 选择堆 4，A 将选择堆 3，并以总计 9 颗石子获胜，B 获得 8 颗石子。
• 否则 A 将选择堆 4，并以总计 10 颗石子获胜，B 将获得 7 颗石子。

示例 2

石子堆：{6,2,4,6}

• 获胜者是 A。

约束

• 2 <= p.length <= 500
• 长度为偶数。
• 1 <= p[i] <= 500
• sum(p[i]) 为奇数。

1. 动态规划法

算法

1. 首先，创建一个包含石子堆的列表。
2. 创建一个二维 DP 数组 并用零值填充它。
3. 当剩余的堆是 p[i], p[i+1],... p[j] 时，每个玩家都有两个选择；因此，玩家的概率可以通过将 j-i 与 n 模 2 进行比较来计算。
4. 玩家 A 选择 p[i] 或 p[j] 以获得尽可能多的石子。
5. 为了减少石子数量，玩家 B 选择 p[i] 或 p[j]。
6. 如果 A 拥有更多石子，则返回 true。

伪代码

示例 1

让我们举一个例子来说明 C++ 中的石子游戏。

输出

复杂度分析

时间复杂度

• O(n^2)

空间复杂度

• O(n^2)

2. 观察法

鉴于玩家 A 首先选择石子堆，并且有偶数堆石子，需要注意的是，玩家 A 总是可以选择奇数或偶数堆。

假设

如果玩家 A 希望选择偶数位置的堆并选择第一堆（即索引为 0 的堆），则玩家 B 可以选择 piles[1] 或 piles[n-1]。玩家 B 只能选择奇数位置的堆，而玩家 A 在每回合都可以选择偶数位置的堆。

算法

• 它初始化一个包含石子堆的列表或数组。
• 返回 True。

示例 2

输出

复杂度分析

时间复杂度

• O(1)

空间复杂度

• O(1)

结论

总之，我们可以通过实施上述两种策略中的任何一种，有效地找出两人之间石子游戏的赢家。这些是解决此石子游戏问题的不同方法。