lintcode 中等题:Coins in Line II 硬币排成线 II
有 n
个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币,直到没有硬币为止。计算两个人分别拿到的硬币总价值,价值高的人获胜。
请判定 第一个玩家 是输还是赢?
给定数组 A = [1,2,2]
, 返回 true
.
给定数组 A = [1,2,4]
, 返回 false
.
解题
动态规划、博弈论
坑死,看了好久
定义dp[i]表示从i到end能取到的最大值
当我们在i处,有两种选择:
1.若取values[i],对方可以取values[i+1] 或者values[i+1] + values[i+2]
当对方取values[i+1] 后 ,我们只能从 i+2 到end内取,我们所取得最大值是dp[i+2], 注意:对方所选取的结果一定是使得我们以后选取的值最小
当对方取values[i+1] + values[i+2]后,我们只能从i+3到end内取,我们所取得最大值是dp[i+3]。
此时:dp[i] = values[i] + min(dp[i+2],dp[i+3]) , 注意:对方所选取的结果一定是使得我们以后选取的值最小
2.若取values[i] + values[i+1],对方可取values[i+2] 或者values[i+2] + values[i+3]
当对方取values[i+2]后,我们只能从i+3到end内取,我们取得最大值是dp[i+3]
当对方取values[i+2]+values[i+3]后,我们只能从i+4到end内去,我们取得最大值是dp[i+4]
此时:dp[i] = values[i] + values[i+1]+min(dp[i+3],dp[i+4])
这里的取最小值和上面一样的意思,对方选取过之后的值一定是使得我们选取的值最小,对方不傻并且还很聪明
最后我们可以取上面两个dp[i]的最大值,就是答案,这里意思是:对方留得差的方案中,我们选取的最大值。
Read full article from lintcode 中等题:Coins in Line II 硬币排成线 II
No comments:
Post a Comment