我正在尝试使用动态编程解决点游戏的变体。
常规的点游戏是用一排点来玩的。每个玩家在他们各自的线端取一个或两个点，没有点的人获胜。
在这个版本的游戏中，每个点都有不同的值。每个玩家轮流轮流，并在线路的两端取任意一个点。我想想出一种方法来使用动态编程来找到第一个玩家可以保证获胜的最大金额。
我在解决这个问题并试图为解决方案编写重复出现时遇到问题。任何帮助表示赞赏，谢谢！
问问题
2297 次
1 回答
4
看看这个网站： http: //people.csail.mit.edu/bdean/6.046/dp/，尤其是第 10 题：
游戏的最佳策略。考虑一排 n 个值 v(1) ... v(n) 的硬币，其中 n 是偶数。我们通过交替轮流与对手进行游戏。在每一轮中，玩家从该行中选择第一个或最后一个硬币，将其从该行中永久移除，并获得硬币的价值。确定如果我们先行动，我们绝对可以赢得的最大可能金额。
如果我没看错你的帖子，这正是你想要的。解决方案非常简单，我认为它在那里解释得很好。
于 2010-05-04T09:24:55.213 回答