0877. Stone Game

题目信息

题号:

0877

难度:

Medium

主题:

双人博弈、数组两端、最优策略

原题:

LeetCode 0877

重点:

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 获胜。