1140. Stone Game II

题目信息

题号:

1140

难度:

Medium

主题:

双人博弈、动态规划、最优策略

原题:

LeetCode 1140

重点:

每回合从剩余石堆最前端取 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 颗石子。