0877. Stone Game¶
题目信息¶
- 题号:
0877
- 难度:
Medium
- 主题:
双人博弈、数组两端、最优策略
- 原题:
- 重点:
Alice 先手,双方每回合只能取最左或最右一堆并都按最优策略行动;石子总数为奇数,因此不会平局
题目重述¶
桌上有偶数堆石子,按数组 piles 从左到右排列。Alice 与 Bob 轮流行动,Alice 先手。每回合当前玩家必须拿走最左端或最右端的一整堆石子,并获得其中全部石子;直到所有堆都被拿完。
双方都采用使自己最终获胜的最优策略。所有石子总数为奇数,因此两人的得分不会相同。请返回 Alice 最终获得的石子是否多于 Bob。
2 <= piles.length <= 500,堆数为偶数,1 <= piles[i] <= 500,所有石子总数为奇数。
自建示例¶
先手可固定取得更有利的一组位置:
输入:piles = [3,7,2,5]
输出:true
解释:Alice 先取右端的 5。无论 Bob 接着取 3 还是 2,Alice 都能取得 7,最终至少获得 12 个石子并获胜。
只有两堆石子:
输入:piles = [2,3]
输出:true
解释:堆数达到允许的最小值 2。Alice 第一回合直接拿走右端的 3,Bob 只能拿剩余的 2,因此 Alice 获胜。