Java 中的石头游戏

在此游戏中，石头排成一排（给定一个输入数组）。有两个玩家，他们负责拾取价值最大的石头。收集到价值最大石头者赢得游戏。玩家 1 先手。然后玩家 2 依次进行。一次，玩家可以选择拾取 1、2 或 3 块石头。石头必须仅从左侧拾取。请注意，玩家必须拾取至少一块石头。我们的任务是确定如果双方玩家都以最优方式进行游戏，谁将赢得游戏。

示例 1

int arr[] = {4, 3, 9, 16}

输出：玩家 1 和玩家 2 打平

解释：由于石头是从左侧拾取的，并且最多只能拾取三块石头，玩家 1 只能拾取石头 1、2 和 3。因此，拾取的石头的总价值为 4 + 3 + 9 = 16。现在轮到玩家 2 了。玩家 2 可以拾取价值为 16 的石头 4。因此，双方玩家获得了相同的价值。因此，打平。

示例 2

int arr[] = {8, -1, -1, 7}

输出：玩家 1 赢得游戏。

解释：玩家 1 以最优方式进行游戏。玩家 1 只拾取左侧的第一块石头，其余石头留下。因此，玩家 1 的总价值为 8。现在轮到玩家 2 拾取石头了。由于玩家只能从左侧拾取石头；因此，玩家 2 必须拾取价值为 -1、-1 和 7 的石头。因此，玩家 2 拾取的总价值为 -1 + -1 + 7 = 5，小于 8。因此，玩家 1 获胜。

示例 3

int arr[] = {-7, 2, 6, 3}

输出：玩家 2 赢得游戏。

解释：为了获得最大价值，玩家 1 拾取石头 1、2 和 3。因此，收集到的最大价值为 -7 + 2 + 6 = 1。只剩下一块石头被玩家 2 拾取。这块石头的价值是 3。因此，玩家 2 赢得游戏。

示例 4

int arr[] = {1, 2, 0, 3, 6, 7, 4}

输出：玩家 1 赢得游戏。

解释：为了获得最大价值，玩家 1 只拾取石头 1 和 2。因此，收集到的最大价值为 1 + 2 = 3。现在轮到玩家 2 了，玩家 2 拾取价值为 0、3 和 6 的石头（总价值 0 + 3 + 6 = 9）。再次轮到玩家 1 了，玩家 1 拾取 7 和 4。因此，玩家 1 收集到的总价值为 3 + 7 + 4 = 14，大于 9。因此，玩家 1 赢得游戏。

方法：使用递归

这是一种暴力破解方法，我们考虑了玩家的每一种可能情况。第一种情况是玩家只拾取一块石头。第二种情况是玩家拾取两块石头。第三种情况是玩家拾取三块石头。这三种情况的最大值就是玩家获得的价值。请看下面的程序。

文件名： StoneGame.java

输出

For the stones of the following values: 
4 3 9 16 
It is a tie between player 1 and player 2

For the stones of the following values: 
8 -1 -1 7 
Player 1 wins the game.

For the stones of the following values: 
-7 2 6 3 
Player 2 wins the game.

For the stones of the following values: 
1 2 0 3 6 7 4 
Player 1 wins the game.

复杂度分析：该程序的时间复杂度是指数级的，因为有递归调用来处理所有情况。

由于上述程序的时间复杂度很高，对于较大的输入来说并不适用，它会花费很多时间。

方法：使用迭代（动态规划）

我们假设 dp[j] 是玩家 1 可以获得的最大价值。由于玩家 1 可以拾取 1 到 3 块石头，玩家 2 可以从 dp[j + 1]、dp[j + 2] 或 dp[j + 3] 开始。玩家 2 也可以拾取 1 到 3 块石头。因此，导致 dp[j + 2 至 4]、dp[j + 3 至 5] 和 dp[j + 4 至 6] 的最小值。因此，

如果任何索引超出边界，则表示值为 0。最终得分存储在 dp[0] 中。

文件名： StoneGame1.java

输出

For the stones of the following values: 
4 3 9 16 
It is a tie between player 1 and player 2

For the stones of the following values: 
8 -1 -1 7 
Player 1 wins the game.

For the stones of the following values: 
-7 2 6 3 
Player 2 wins the game.

For the stones of the following values: 
1 2 0 3 6 7 4 
Player 1 wins the game.

复杂度分析：该程序的 time complexity 为 O(3 * N)。在渐近时间复杂度方面，它是 O(N)。由于程序使用了两个辅助数组来存储答案和石头价值的总和，因此 space complexity 为 O(N + N)，即 O(2 *N)。在渐近时间方面，它仍然是 O(N)，其中 N 是石头数组中的元素总数。

程序的空间复杂度可以进一步降低。我们可以使用变量而不是数组，这在下面的程序中得到了体现。

文件名： StoneGame1.java

输出

For the stones of the following values: 
4 3 9 16 
It is a tie between player 1 and player 2

For the stones of the following values: 
8 -1 -1 7 
Player 1 wins the game.

For the stones of the following values: 
-7 2 6 3 
Player 2 wins the game.

For the stones of the following values: 
1 2 0 3 6 7 4 
Player 1 wins the game.

复杂度分析：该程序的时间复杂度与前一个程序相同。由于程序只使用了变量而不是数组，因此 space complexity 是常数，即 O(1)。