一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请号
扫码关注留学申请公众号
查看: 768|回复: 9
收起左侧

[动态规划] [G 家 onsite 题] 探讨 Stone Game (LC877) 的扩展:3 个 player 的 Stone Game

[复制链接] |只看干货
我的人缘0

升级   24%


分享帖子到朋友圈
wmy5 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (54)
 
 
3% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 wmy5 于 2020-11-25 10:30 编辑

Stone Game 大家应该很熟悉了,这里简单说一下:

有 N 堆石头排列成一排,用数组 piles[0, ..., N-1] 表示,piles 代表第 i 堆石头的个数。两个玩家轮流从 piles[] 里拿石头,每次可以拿 1、2 或 3 堆(不能不拿,且如果拿了某堆,就要把该堆石头全部拿走)。最终当 piles 被拿完时,石头总数多的一方获胜。

两个玩家时,是零和游戏,所以可以用 DP + Minmax 的方式解决。但是当三个玩家时候(其它规则不变,游戏顺序:玩家 1、玩家 2、玩家 3),应该怎么解这道题呢?

G 家 virtual onsite 时候遇到了这个题(三人),lz 没解出来。

补充内容 (2020-11-26 00:47):
补充一下:忽略一个细节,和 LC 原题不一样的是,只能从头拿:

拿 piles[0]
拿 piles[0], piles[1]
拿 piles[0], piles[1], piles[2]

评分

参与人数 1大米 +10 收起 理由
14417335 + 10

查看全部评分


上一篇:面试高频题型总结,上岸回馈
下一篇:今年毕业明年研究生入学暑假身份问题
无效楼层,该帖已经被删除
我的人缘0

升级   24%

 楼主| wmy5 2020-11-25 11:31:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (54)
 
 
3% (2)    👎
愤怒的小蚯蚓 发表于 2020-11-25 11:24
我去....三个人?

补充内容 (2020-11-25 11:25):

我也是这么觉得,因为不再是零和了。
回复

使用道具 举报

无效楼层,该帖已经被删除
我的人缘0

升级   24%

 楼主| wmy5 2020-11-25 12:01:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (54)
 
 
3% (2)    👎
愤怒的小蚯蚓 发表于 2020-11-25 11:55
还是零和,只是 是 多方的零和博弈...

补充内容 (2020-11-25 11:56):

这么说也对,但是多方的话确实不知道应该如何下手。
回复

使用道具 举报

无效楼层,该帖已经被删除
我的人缘0

升级   89.86%

心之邑 2020-11-25 23:13:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (30)
 
 
0% (0)    👎
三个player每人max自己的score应该就可以了吧,三维dp或者recursion with memorization

a(i,j) -> (score_a, score_b, score_c) : max score a can achieve if a starts picking a pile in the current settings
b(i,j) -> (score_a, score_b, score_c) : max score b can achieve if b starts picking a pile in the current settings
c(i,j) -> (score_a, score_b, score_c) : max score c can achieve if c starts picking a pile in the current settings

a(i,j)计算方法:
if i ==j:
    a(i,j) = (piles,0,0)
else:
    ah,bh,ch = b(i+1,j)
    at,bt,ct = b(i,j-1)
    if ah+piles >  at+piles[j] or ah+piles ==  at+piles[j] and max(bh,ch)<=max(bt,ct):
        a(i,j) = (ah+piles, bh,ch)
   else:
        a(i,j) = (at+piles[j], bt,ct)
把a(i,j)存一下加速计算。
要考虑break tie的情况因为现在有3个人,取头尾都一样的话应该取让除了当前player之外的最高的那个人少拿的case

补充内容 (2020-11-26 02:07):
a(i,j)意思是现在轮到a来拿,piles现在可以拿的pile是从i到j的这些piles

评分

参与人数 1大米 +10 收起 理由
14417335 + 10

查看全部评分

回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
我的人缘0

升级   20.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (298)
 
 
0% (0)    👎
只能从头尾拿?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表