0877. 石子游戏

• 标签：数组、数学、动态规划、博弈
• 难度：中等

题目链接

• 0877. 石子游戏 - 力扣

题目大意

亚历克斯和李在玩石子游戏。总共有偶数堆石子，每堆都有正整数颗石子 piles[i]，总共的石子数为奇数 。每回合，玩家从开始位置或者结束位置取走一整堆石子。直到没有石子堆为止结束游戏，最终手中石子颗数多的玩家获胜。假设亚历克斯和李每回合都能发挥出最佳水平，并且亚历克斯先开始。

给定代表每个位置石子颗数的数组 piles。

要求：判断亚历克斯是否能赢得比赛。如果亚历克斯赢得比赛，则返回 True。如果李赢得比赛返回 False。

解题思路

能取的次数是偶数个，总数是奇数个。

• 如果亚历克斯开始取了开始偶数位置 0，那么李只能取奇数位置 1 或者末尾位置 len(piles) - 1。然后亚历克斯可以j接着取偶数位。
• 或者亚历克斯开始取了最后奇数位置 len(piles) - 1，那么李只能取偶数位置 0 或 len(piles) - 2。然后亚历克斯可以接着取奇数位。
• 这样亚历克斯只要一开始计算好奇数位置上的石子总数多，还是偶数位置上的石子总数多，然后就可以选择一开始取奇数位置还是偶数位置。所以最后肯定会赢
• 游戏一开始，其实就没李啥事了。。。

代码

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True