• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

技术杂谈 勤劳的小蚂蚁 2周前 (03-09) 21次浏览 未收录 0个评论 扫描二维码

题目来源于 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;
    }
}
看完之后,你的心情是怎么样的?

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:一道看完答案你会觉得很沙雕的「动态规划算法题」
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00