1140. Stone Game II¶
题目信息¶
- 题号:
1140
- 难度:
Medium
- 主题:
双人博弈、动态规划、最优策略
- 原题:
- 重点:
每回合从剩余石堆最前端取
1至2M堆,随后令M = max(M, X);Alice 先手并最大化自己最终获得的石子数
题目重述¶
石堆按数组 piles 从左到右排列。Alice 和 Bob 轮流行动,Alice 先手。初始 M = 1;轮到玩家时,可以取走剩余序列最前面的 X 堆,其中 1 <= X <= 2M,随后把 M 更新为 max(M, X)。
游戏持续到所有石堆都被取走。假设双方都采用最优策略,请返回 Alice 最终能够获得的最大石子总数。
1 <= piles.length <= 100,1 <= piles[i] <= 10^4。
自建示例¶
先取两堆获得最优结果:
输入:piles = [1,2,3]
输出:3
解释:Alice 初始可以取一堆或两堆。取前两堆可获得 3 颗,Bob 随后取走最后一堆;若只取第一堆,Bob 可以取走剩余两堆。
只有一堆石子:
输入:piles = [7]
输出:7
解释:Alice 首回合直接取走唯一石堆,获得全部 7 颗石子。