1406. Stone Game III¶
题目信息¶
- 题号:
1406
- 难度:
Hard
- 主题:
动态规划、博弈、后缀状态
- 原题:
- 重点:
两人轮流从数组开头取一至三堆,得分为石子值之和;双方采用最优策略,返回胜者或平局
题目重述¶
石子堆按数组 stoneValue 从左到右排列。Alice 先手,两人轮流从当前最左端取走 1、2 或 3 堆,并把所取石子值加入自己的总分,直到所有堆被取完。
双方都采用最优策略。Alice 得分更高时返回 "Alice",Bob 更高时返回 "Bob",得分相同返回 "Tie"。
1 <= stoneValue.length <= 5 * 10^4,-1000 <= stoneValue[i] <= 1000。
自建示例¶
先手可以避开末尾负值确保获胜:
输入:stoneValue = [2,1,-5]
输出:"Alice"
解释:Alice 取前两堆可得 3 分,Bob 只能取到 -5 分,因此 Alice 获胜。
唯一石子值为零时平局:
输入:stoneValue = [0]
输出:"Tie"
解释:Alice 取走唯一石子堆后双方得分都为零。