一道看完答案你会觉得很沙雕的「动态规划算法题」

一道看完答案你会觉得很沙雕的「动态规划算法题」

这道算法题其实并不难,如果你把文章从头到尾看完的话基本上能看懂,但如果你看到最后的话大概率会说一句:这是什么沙雕题目?!

题目来源于 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-iN 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);我们想要其中的最小可能得分。

代码如下:

一道看完答案你会觉得很沙雕的「动态规划算法题」
图 1

上面的代码并不算复杂,当然,如果你看不懂也没关系,不影响解决问题,请看下面的数学分析。

数学分析

因为石头的数量是奇数,因此只有两种结果,输或者赢。

喜羊羊先开始拿石头,随便拿!然后比较石头数量:

  1. 如果石头数量多于对手,赢了;

  2. 如果石头数量少于对手,自己拿石头的顺序和对手拿石头的顺序对调,还是赢。

所以代码如下:

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

看完之后,你的心情是怎么样的?

此题的 LeetCode 的评论区里一片吐槽:这是什么沙雕题目!

可能搞过 ACM 等竞赛的人都会微微一笑:不会几万个套路怎么好意思说自己是 acmer 。我们这些普通人为之惊奇的题目,到他们这里就是彻底被玩坏了,各种稀奇古怪的秒解。

End

一道看完答案你会觉得很沙雕的「动态规划算法题」


今日问题:


你还见过哪些可以用数学思维解决的算法题目,可以分享分享。或者你觉得这类题目的意义是什么,考察的是什么。


打卡格式:

打卡 X 天,答:xxx 。


 

一道看完答案你会觉得很沙雕的「动态规划算法题」

欢迎关注这个会做动画的程序员👆


如果文章有帮助,点个“好看”吧!
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 一道看完答案你会觉得很沙雕的「动态规划算法题」

我还会在以下平台发布内容

GitHub 哔哩哔哩