请教一道动态规划算法题

进来学习

【 在 lida 的大作中提到: 】 : 问题：一个拿数字游戏：在一个堆栈里压入n个数字，玩家可以看到每一个数字，游戏规则如下：玩家轮流从堆栈里取出1-2个数字，直到堆栈空为止，谁得到的数字之和最大谁赢。如果玩家都是游戏好手，如果你有先拿或者后拿的选择权利，如何设计一个算法来进行选择使得你自己保持不败？ : 没有思路，求分析，最好能给出递归式，谢谢 说下自己的想法，轻拍 先只考虑先手的情况 自己先拿一个或者两个， 然后最优策略模拟对手去接着玩（相对于对手是接下来的先手），计算对手获得的最大值，剩下的就是自己获得最大值。 上边的算完后，先手后手的最优策略都有了。 把堆栈当成数组nums，nums[0]为栈底 sum数组，sum[k]为nums[0...k]的和 max数组，max[k]为，在先手的情况下，用[0, k]元素玩游戏的最大和，当k <= 2 时max[k] = sum[k] 然后 max[k] = MAX(num[k] + sum[k - 1] - max[k-1]), num[k] + num[k-1] + sum[k - 2] - max[k-2]) 然后算MAX(max[k], sum[k]-max[k]) 感觉先用递归函数比较好想 ———— 微博 @flowmemo , 现在主要写JavaScript. 关注广泛, 欢迎交流. 此签名通过「北邮人签名档」脚本发送

【 在 lida 的大作中提到: 】 : 问题：一个拿数字游戏：在一个堆栈里压入n个数字，玩家可以看到每一个数字，游戏规则如下：玩家轮流从堆栈里取出1-2个数字，直到堆栈空为止，谁得到的数字之和最大谁赢。如果玩家都是游戏好手，如果你有先拿或者后拿的选择权利，如何设计一个算法来进行选择使得你自己保持不败？ : 没有思路，求分析，最好能给出递归式，谢谢 是两个玩家？

谢谢，问题解决了。早上起来仔细想了一下，状态转移方程是catch_max[k]=max{all_sum-catch_max[k-1],all_sum-catch_max[k-2]。已经通过代码验证。再次感谢，昨天就是想不到把catch_max放在减数里，果然脑子不清醒不能看算法题? 【 在 e97ace 的大作中提到: 】 :

最后的问号是符号表情，不知为何变成问号了，手机党伤不起= = 【 在 lida 的大作中提到: 】 : 谢谢，问题解决了。早上起来仔细想了一下，状态转移方程是catch_max[k]=max{all_sum-catch_max[k-1],all_sum-catch_max[k-2]。已经通过代码验证。再次感谢，昨天就是想不到把catch_max放在减数里，果然脑子不清醒不能看算法题?

是的，两个玩家 【 在 dxy1 的大作中提到: 】 :

尼姆游戏？

差不多，只是给定的一列数有序，取数只能从一边取1-2个，最后取数求和大的人赢～ 【 在 l11x0m7 的大作中提到: 】 : 尼姆游戏？

【 在 lida 的大作中提到: 】 : 谢谢，问题解决了。早上起来仔细想了一下，状态转移方程是catch_max[k]=max{all_sum-catch_max[k-1],all_sum-catch_max[k-2]。已经通过代码验证。再次感谢，昨天就是想不到把catch_max放在减数里，果然脑子不清醒不能看算法题? : : 麻烦问下题目在哪儿？能否给个链接？