我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划法 >

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

归档日期:04-23       文本归类:动态规划法      文章编辑:爱尚语录

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

  喜羊羊和灰太狼用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

  喜羊羊和灰太狼轮流进行,喜羊羊先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

  假设喜羊羊和灰太狼都发挥出最佳水平,当喜羊羊赢得比赛时返回 true ,当灰太狼赢得比赛时返回 false 。

  如果灰太狼拿走前 3 颗,那么剩下的是 [ 4,5 ],喜羊羊拿走后 5 颗赢得 10 分。

  如果灰太狼拿走后 5 颗,那么剩下的是 [ 3,4 ],喜羊羊拿走后 4 颗赢得 9 分。

  这表明,取前 5 颗石子对喜羊羊来说是一个胜利的举动,所以我们返回 true 。

  灰太狼肯定会在剩下的这一行中取走前 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(有向无环图)。)

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

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

本文链接:http://quangdungfc.net/dongtaiguihuafa/53.html