点游戏和动态编程

Question

我正在尝试通过动态编程来解决DOT游戏的变体。

常规的点游戏带有一系列点。每个玩家在线的各个末端都取一个或两个点，而那些没有圆点的人取得了胜利。

在此版本的游戏中，每个点具有不同的值。每个玩家都需要替代转弯，并在线路的任一端进行任一点点。我想提出一种使用动态编程来找到保证第一个球员可以赢得的最大金额的方法。

我在抓住这个问题时遇到问题，并试图为解决方案编写复发。任何帮助将不胜感激，谢谢！

Answer 1

看看这个网站： http://people.csail.mit.edu/bdean/6.046/dp/, ，尤其是问题编号10：

游戏的最佳策略。考虑一排值v（1）... v（n）的n行，其中n为n。我们通过交替的转弯与对手进行比赛。在每个回合中，玩家从行中选择第一个或最后一枚硬币，将其从行永久删除，并接收硬币的值。确定如果我们先移动，我们绝对可以赢的最大金额。

如果我正确阅读您的帖子，这正是您想要的。解决方案非常简单，在我看来，它很好地解释了。