最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 题目来源于 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;
        }
    }
    看完之后,你的心情是怎么样的?
    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 一道看完答案你会觉得很沙雕的「动态规划算法题」

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 102会员总数(位)
    • 3674资源总数(个)
    • 2本周发布(个)
    • 0 今日发布(个)
    • 135稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级