一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 361|回复: 4
收起左侧

[动态规划] 问一道题 coins in line II

[复制链接] |试试Instant~ |关注本帖
33847682 发表于 2016-10-11 12:15:01 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
dp[i] = values[i] + Math.min(dp[i+2],dp[i+3]);
dp[i] = Math.max(dp[i],values[i]+values[i+1]+ Math.min(dp[i+3],dp[i+4]));
状态转移方程大概是这样 我想问这里为什么要最小化选手1可以取得硬币的值 题目只是问选手1是赢还是输没有必要取最坏情况吧?
这里取max不行吗?让对手都选最少的 取最好的情况 看能不能赢
stellari 发表于 2016-10-12 08:15:42 | 显示全部楼层
题目虽然没有明说, 但是问你"will XXX win"的题, 一般都暗含"双方都采取最优策略"这个假设, 否则这题就没什么意思了. 所以, 之所以状态转移方程要"最小化选手1可以在i以后取得硬币的值", 是因为选手2为了获胜一定会这么做, 因此状态转移方程必须模拟对手的这个策略.
回复 支持 反对

使用道具 举报

 楼主| 33847682 发表于 2016-10-12 09:46:31 | 显示全部楼层
stellari 发表于 2016-10-12 08:15
题目虽然没有明说, 但是问你"will XXX win"的题, 一般都暗含"双方都采取最优策略"这个假设, 否则这题就没什 ...

多谢大神 所以这种博弈论的题目都是要考虑自己可以选择的最差选择里面取最优?
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-12 12:47:47 | 显示全部楼层
33847682 发表于 2016-10-12 09:46
多谢大神 所以这种博弈论的题目都是要考虑自己可以选择的最差选择里面取最优?

这是一种可行的思路. 另外你也可以这样考虑: 令dp[ i ]为"到游戏结束为止, 在i处先拿的人比后拿的人能够多拿的面值".  如果i处先拿的人只拿1枚, 那么在i处他比对方多拿values[ i ], 但是在i+1~N处,对手可以比他多拿dp[ i+1 ], 也就是他比对手多拿-dp[ i + 1]. 因此从i到N, 他比对方多拿values[ i ]-dp[ i+1 ];同理, 如果先拿的人拿2枚, 那么能比对方多拿values[ i ] + values [ i + 1] - dp[ i + 2] .取这二者最大值即可得 dp [ i ], 最后看dp [ 0 ] 是大于还是小于 0 即可. 这样的话, 状态转移方程会比你说的那个解法要简单些, 而且也没有"最差选择"这种思维方式.
回复 支持 反对

使用道具 举报

 楼主| 33847682 发表于 2016-10-12 13:12:57 | 显示全部楼层
stellari 发表于 2016-10-12 12:47
这是一种可行的思路. 另外你也可以这样考虑: 令dp[ i ]为"到游戏结束为止, 在i处先拿的人比后拿的人能够 ...

明白了 那像这种minmax的题目都可以像你说的这种方法去考虑嘛? 比如Guess Number Higher or Lower II这道题 用minmax是可以做出来的 用你的想法可以做嘛?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 01:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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