总结LeetCode上石头游戏这一类型的几道题

2021-11-21

Algorithm

第一题

LeetCode 877 Medium [ https://leetcode.com/problems/stone-game ]

描述：

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家获胜。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

输入：

一个整数数组
输出：

true 或 false
样例输入1：

[5,3,4,5]
样例输出1：

true

说明：
- Alice 先开始，只能拿前 5 颗或后 5 颗石子。
- 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
- 如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
- 如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
- 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。
样例输入2：

[3,7,2,3]
样例输出2：

true
数据范围

$2 <= piles.length <= 500$

$ 1 <= piles[i] <= 500 $
解题思路：
- 解法一：DFS，用player变量区分轮到Alice还是Bob，分别递归调用取最左边那一堆和最右边那一堆的情况，石子全部取完后判断Alice总数是否大于Bob总数，是则赢，否则输。两种递归情况只要有一个返回true即可表示Alice能赢。
- 解法二：DP，用一个二维DP数组，dp[i][j]表示在区间[i, j]内Alice比Bob多拿的石子数，最后dp[0][n-1]大于0则表示Alice能赢。在区间[i, j]内分情况讨论：若Alice拿了piles[i]，那么dp[i+1][j]表示Bob比Alice多拿的石子数，piles[i]-dp[i+1][j]就是Alice比Bob多拿的石子数；若Alice拿了piles[j]，那么dp[i][j-1]表示Bob比Alice多拿的石子数，piles[j]-dp[i][j-1]就是Alice比Bob多拿的石子数。两种情况取最大值即可更新dp[i][j]，注意，这里的更新顺序是从小区间向大区间更新，初始化长度为1的区间dp[i][i]为piles[i]。
- 解法三：脑筋急转弯，因为总共有偶数堆石子，所以可以按奇偶分成堆数相等的两份，又因为石子总数为奇数，所以分成的两份的石子数一定不相等，总存在一份大于另一份。如果按奇数堆分的那一份大于按偶数堆分的那一份，那么Alice每次取奇数堆最后总会赢，反之，每次取偶数堆也总会赢。

参考代码:

代码1，DFS（现在已TLE）

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return helper(piles, 0, 0, 0, (int)piles.size() - 1, 0);
    }
    bool helper(vector<int>& piles, int aliceNum, int bobNum, int left, int right, int player) {
        if(left>right) return aliceNum>bobNum;
        if(player==0) { //轮到Alice
            return helper(piles, aliceNum+piles[left], bobNum, left+1, right, 1)
                || helper(piles, aliceNum+piles[right], bobNum, left, right-1, 1);
        } else { //轮到Bob
            return helper(piles, aliceNum, bobNum+piles[left], left+1, right, 0)
                || helper(piles, aliceNum, bobNum+piles[right], left, right-1, 0);
        }
    }
};

代码2，DP

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n=piles.size(), dp[n][n];
        for(int i=0;i<n;i++) dp[i][i]=piles[i];
        for(int len=1;len<n;len++) {
            for(int i=0;i<n-len;i++) {
                int j=i+len;
                dp[i][j]=max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1]>0;
    }
};

代码3，脑筋急转弯

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

第二题

LeetCode 1140 Medium [ https://leetcode.com/problems/stone-game-ii ]

描述：

Alice 和 Bob 继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

Alice 和 Bob 轮流进行，Alice 先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 可以得到的最大数量的石头。
输入：

一个整数数组
输出：

一个整数
输入样例1：

[2,7,9,4,4]
输出样例1：

10

说明：
- 如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。
输入样例2：

[1,2,3,4,5,100]
输出样例2：

104
数据范围：

$ 1 <= piles.length <= 100 $

$ 1 <= piles[i] <= 10^4 $
解题思路：动态规划

参考代码：

代码1，DP

class Solution {
public:
    int stoneGame(vector<int>& piles) {
        int n=piles.size();
        vector<int> sums=piles;
        vector<vector<int>> dp(n+1, vector<int>(n+1));
        for(int i=n-2;i>=0;i--) {
            sums[i]+=sums[i+1];
        }
        for(int i=0;i<n;i++) {
            dp[i][n]=sums[i];
        }
        for(int i=n-1;i>=0;i--) {
            for(int m=n-1;m>=1;m--) {
                for(int x=1;x<=2*m && i+x<=n;++x) {
                    dp[i][m]=max(dp[i][m],sums[i]-dp[i+x][max(x,m)]);
                }
            }
        }
        return dp[0][1];
    }
};

代码2，带记忆数组的递归

class Solution {
public:
    int stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<int> sums = piles;
        vector<vector<int>> memo(n, vector<int>(n));
        for (int i = n - 2; i >= 0; --i) {
            sums[i] += sums[i + 1];
        }
        return helper(sums, 0, 1, memo);
    }
    int helper(vector<int>& sums, int i, int m, vector<vector<int>>& memo) {
        if (i + 2 * m >= sums.size()) return sums[i];
        if (memo[i][m] > 0) return memo[i][m];
        int res = 0;
        for (int x = 1; x <= 2 * m; ++x) {
            int cur = sums[i] - sums[i + x];
            res = max(res, cur + sums[i + x] - helper(sums, i + x, max(x, m), memo));
        }
        return memo[i][m] = res;
    }
};

第三题

LeetCode 1406 Hard [ https://leetcode.com/problems/stone-game-iii ]

描述：

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 **1、2 或 3 堆石子 **。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ，Bob 赢了就返回 “Bob”，平局（分数相同）返回 “Tie” 。
输入：

一个整数数组
输出：

“Bob” 或 “Alice” 或 “Tie”
输入样例1：

[1,2,3,7]
输出样例1：

“Bob”

说明：
- Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。
输入样例2：

[1,2,3,-9]
输出样例2：

“Alice”

说明：
- Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
- 如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
- 如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
- 注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

输入样例3：

[1,2,3,6]
输出样例3：

“Tie”

说明：
- Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。
输入样例4：

[1,2,3,-1,-2,-3,7]
输出样例4：

“Alice”
输入样例5：

[-1,-2,-3]
输出样例5：

“Tie”
数据范围：

$ 1 <= stoneValue.length <= 50000 $

$ -1000 <= stoneValue[i] <= 1000 $
解题思路：
参考代码：
1

第四题

LeetCode 1510 Hard [ https://leetcode.com/problems/stone-game-iv ]

描述：

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走任意非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 true ，否则返回 false 。
输入：

一个整数
输出：

true 或 false
输入样例1：

1
输出样例1：

true

说明：
- Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
输入样例2：

2
输出样例2：

false

说明：
- Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
输入样例3：

4
输出样例3：

true

说明：
- n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
输入样例4：

7
输出样例4：

false

说明：
- 当 Bob 采取最优策略时，Alice 无法赢得比赛。
- 如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
- 如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
输入样例5：

17
输出样例5：

false

说明：
- 如果 Bob 采取最优策略，Alice 无法赢得胜利。
数据范围：

$ 1 <= n <= 10^5 $
解题思路：
参考代码：
1

第五题

LeetCode 1563 Hard [ https://leetcode.com/problems/stone-game-v ]

描述：

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。
输入：

一个整数数组
输出：

一个整数
输入样例1：

[6,2,3,4,5,5]
输出样例1：

18

说明：
- 在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
- 在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
- 最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
输入样例2：

[7,7,7,7,7,7,7]
输出样例2：

28

输入样例3：

[4]
输出样例3：

0

数据范围：

$ 1 <= stoneValue.length <= 500 $

$ 1 <= stoneValue[i] <= 10^6 $
解题思路：动态规划
参考代码：
1

第六题

LeetCode 1686 Medium [ https://leetcode.com/problems/stone-game-vi ]

描述：

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以移出一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：
- 如果 Alice 赢，返回 1 。
- 如果 Bob 赢，返回 -1 。
- 如果游戏平局，返回 0 。
输入：

两个长度相等的整数数组
输出：

1 或 -1 或 0
输入样例1：

[1,3] [2,1]
输出样例1：

1

说明：
- 如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
- Bob 只能选择石子 0 ，得到 2 分。
- Alice 获胜。

输入样例2：

[1,2] [3,1]
输出样例2：

0

说明：
- Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
- 打平。
输入样例3：

[2,4,3] [1,6,7]
输出样例3：

-1

说明：
- 不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
- 比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
- Bob 会获胜。

数据范围：

$ 1 <= n <= 10^5 $

$ 1 <= aliceValues[i], bobValues[i] <= 100 $
解题思路：动态规划
参考代码：
- 代码1
  1

第七题

LeetCode 1690 Medium [ https://leetcode.com/problems/stone-game-vii ]

描述：

石子游戏中，Alice 和 Bob 轮流进行自己的回合，Alice 先开始。

有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。

Bob 发现他总是输掉游戏，所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果 Alice 和 Bob 都 发挥出最佳水平 ，请返回他们 得分的差值 。
输入：

一个整数数组
输出：

一个整数

输入样例1：

[5,3,1,4,2]

输出样例1：

6

说明：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。
输入样例2：

[7,90,5,1,100,10,10,2]

输出样例2：

122

数据范围：

$ 2 <= n <= 1000 $

$ 1 <= stones[i] <= 1000 $

解题思路：
参考代码：
1

第八题

LeetCode 1872 Hard [ https://leetcode.com/problems/stone-game-viii ]

描述：

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：
- 选择一个整数 x > 1 ，并且移除最左边的 x 个石子。
- 将移除的石子价值之和累加到该玩家的分数中。
- 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。
当只剩下一个石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用最优策略的情况下，Alice 和 Bob 的 分数之差 。
输入：

一个整数数组
输出：

一个整数

输入样例1：

[-1,2,-3,4,-5]

输出样例1：

5

说明：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。
输入样例2：

[7,-6,5,10,5,-2,-6]

输出样例2：

13

说明：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。
输入样例3：

[-10,-12]

输出样例3：

-22

说明：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。

数据范围：

$n == stones.length$

$2 <= n <= 10^5$

$-10^4 <= stones[i] <= 10^4$

解题思路：动态规划+前缀和

首先要明白一点，不管是谁进行操作，数组的总和是不变的。

这里对玩家操作进行抽象，抽象成对前缀和数组进行操作，所以要预先计算出前缀和数组。一名玩家在石子值前缀和数组中选取第 i 个值，然后另一玩家在 [i + 1, n - 1] 区间内选取下一前缀和数值。

Alice和Bob都会采取最优策略，Alice每次操作要尽量增大他和Bob的分数差，Bob每次操作要尽量减小Alice和他的分数差，实际上就是无论轮到谁操作，都尽量获得最大分数的意思。那么，在同一条件下 Alice 和 Bob 的操作就完全相同。注意：这里求得统一都是且只是（Alice的分数-Bob的分数）。

设计一个动态规划数组dp表示玩家的最优策略即可，dp[i]表示区间 [i, n - 1] 范围内能够获得的最大分数差，则对位置 i，根据是否选取第 i 个前缀和可得到状态转移方程 dp[i] = max(dp[i + 1], preSum[i] - dp[i + 1])。

这里再详细解释一下状态转移方程：如果不选取第i个前缀和，那么区间[i, n-1]范围内能够获得的最大分数差就是区间[i+1, n-1]范围内能够获得的最大分数差。如果选取第i个前缀和，那么区间[i, n-1]范围内能够获得的最大分数差就是选取的第i个前缀和得到的分数减去区间[i+1, n-1]范围内能够获得的最大分数差，之所以减是因为这次和下一次的操作者不同，从下一次操作者的视角来看，dp[i+1]得到的是他与另一个人的最大分数差，而这次操作要求的是操作者与下一次操作者的分数差，即$x1-x2=-(x2-x1)$。

由于第 n - 1 个前缀和一定会被选取，可从后向前进行动态规划。又因为第一次选取操作时只能从第 2 个石子开始，Alice 的有效起始点为 dp[1]，所以最后要求的结果就是dp[1]（区间 [1, n - 1] 范围内能够获得的最大分数差）。

参考代码：

代码1，按照解题思路写的

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n=stones.size();
        vector<int> preSum;
        partial_sum(stones.begin(),stones.end(),back_inserter(preSum));
        //copy(preSum.begin(),preSum.end(),ostream_iterator<int>(cout," "));
        vector<int> dp(n);
        dp[n-1]=preSum[n-1];
        for(int i=n-2;i>=1;i--) {
            dp[i]=max(dp[i+1],preSum[i]-dp[i+1]);
        }
        return dp[1];
    }
};

代码2，另一种解题思路，与代码1的解题思路并无太大区别，动态规划数组定义不同

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n=stones.size();
        vector<int> presum(n+1); // 前缀和数组
        vector<int> dp(n+1); // d
        // 求前缀和数组
        for(int i=1;i<=n;i++) {
            presum[i]=presum[i-1]+stones[i-1];
        }
        dp[1]=0; // 剩一堆石子时，先手-后手 的最大分数差为0
        dp[2]=presum[n]-dp[1];
        for(int i=3;i<=n;i++) {
            dp[i]=max(dp[i-1],presum[n-i+2]-dp[i-1]);
        }
        return dp[n];// 剩n堆石子的最大分数差
    }
};

总结LeetCode上石头游戏这一类型的几道题

第一题

第二题

第三题

第四题

第五题

第六题

第七题

第八题

Previous

Rust新手上路

Rust

Next

总结LeetCode上跳跃游戏这一类型的几道题

DFS Dynamic Programming Greedy BFS LeetCode

Related Posts