这道算法题其实并不难, 如果你把文章从头到尾看完的话基本上能看懂, 但如果你看到最后的话大概率会说一句: 这是什么沙雕题目?!
题目来源于 LeetCode 第 877 号问题: 石子游戏.
为了更好理解, 我改编了一下题目, 描述是这样的:
题目描述
喜羊羊和灰太狼用几堆石子在做游戏. 偶数堆石子排成一行, 每堆都有正整数颗石子 piles[i] .
游戏以谁手中的石子最多来决出胜负. 石子的总数是奇数, 所以没有平局.
喜羊羊和灰太狼轮流进行, 喜羊羊先开始. 每回合, 玩家从行的开始或结束处取走整堆石头. 这种情况一直持续到没有更多的石子堆为止, 此时手中石子最多的玩家获胜.
假设喜羊羊和灰太狼都发挥出最佳水平, 当喜羊羊赢得比赛时返回 true , 当灰太狼赢得比赛时返回 false .
题目分析
举两个例子来帮助理解题意.
例子一:
输入:[ 5,3,4,5 ]
输出: true
解释:
喜羊羊先开始, 只能拿前 5 颗或后 5 颗石子 .
假设他取了前 5 颗, 这一行就变成了 [ 3 ,4,5 ] .
如果灰太狼拿走前 3 颗, 那么剩下的是 [ 4,5 ], 喜羊羊拿走后 5 颗赢得 10 分.
如果灰太狼拿走后 5 颗, 那么剩下的是 [ 3,4 ], 喜羊羊拿走后 4 颗赢得 9 分.
这表明, 取前 5 颗石子对喜羊羊来说是一个胜利的举动, 所以我们返回 true .
例子二:
输入:[ 5,10000,2,3 ]
输出: true
解释:
喜羊羊先开始, 只能拿前 5 颗或后 3 颗石子 .
假设他取了后 3 颗, 这一行就变成了 [ 5,10000,2 ].
灰太狼肯定会在剩下的这一行中取走前 5 颗, 这一行就变成了 [ 10000,2 ].
然后喜羊羊取走前 10000 颗, 总共赢得 10003 分, 灰太狼赢得 7 分.
这表明, 取后 3 颗石子对喜羊羊来说是一个胜利的举动, 所以我们返回 true .
这个例子表明, 并不是需要每次都挑选最大的那堆石头.
题目回答
涉及到最优解的问题, 那么肯定要去尝试一下使用 ** 动态规划 ** 来解决了.
先看一下力扣的正规题解:
让我们改变游戏规则, 使得每当灰太狼得分时, 都会从喜羊羊的分数中扣除.
令 dp(i, j) 为喜羊羊可以获得的最大分数, 其中剩下的堆中的石子数是 piles[i], piles[i+1], ..., piles[j]. 这在比分游戏中很自然: 我们想知道游戏中每个位置的值.
我们可以根据 dp(i + 1,j) 和 dp(i,j-1) 来制定 dp(i,j) 的递归, 我们可以使用动态编程以不重复这个递归中的工作.(该方法可以输出正确的答案, 因为状态形成一个 DAG(有向无环图).)
当剩下的堆的石子数是 piles[i], piles[i+1], ..., piles[j] 时, 轮到的玩家最多有 2 种行为.
可以通过比较 j-i 和 N modulo 2 来找出轮到的人.
如果玩家是喜羊羊, 那么它将取走 piles[i] 或 piles[j] 颗石子, 增加它的分数. 之后, 总分为 piles[i] + dp(i+1, j) 或 piles[j] + dp(i, j-1); 我们想要其中的最大可能得分.
如果玩家是灰太狼, 那么它将取走 piles[i] 或 piles[j] 颗石子, 减少喜羊羊这一数量的分数. 之后, 总分为 -piles[i] + dp(i+1, j) 或 -piles[j] + dp(i, j-1); 我们想要其中的最小可能得分.
代码如下:
上面的代码并不算复杂, 当然, 如果你看不懂也没关系, 不影响解决问题, 请看下面的数学分析.
数学分析
因为石头的数量是奇数, 因此只有两种结果, 输或者赢.
喜羊羊先开始拿石头, 随便拿! 然后比较石头数量:
如果石头数量多于对手, 赢了;
如果石头数量少于对手, 自己拿石头的顺序和对手拿石头的顺序对调, 还是赢.
所以代码如下:
- class Solution {
- public boolean stoneGame(int[] piles) {
- return true;
- }
- }
看完之后, 你的心情是怎么样的?
此题的 LeetCode 的评论区里一片吐槽: 这是什么沙雕题目!
可能搞过 ACM 等竞赛的人都会微微一笑: 不会几万个套路怎么好意思说自己是 acmer . 我们这些普通人为之惊奇的题目, 到他们这里就是彻底被玩坏了, 各种稀奇古怪的秒解.
来源: https://juejin.im/post/5c81c09de51d453a1222295d