问题如下：
有一个游戏由n个数字(a1，a2，a3，..，an(和两个玩家组成。玩家从序列中提取数字；在每个回合中，玩家可以选择序列中的第一个或最后一个数字。当序列被清空时，总数较大的玩家获胜；如果比分相等，这场比赛就是一场平局。
目标是编写一个算法，返回一系列选择，以确保第一个玩家获得最佳结果(获胜或平局(，假设第二个玩家将以最佳方式比赛。
我提出了一个递归公式，可以转化为动态编程解决方案：
- 对于序列Ai，Ai+1，。。。，Aj：
- 如果序列中有一个数字，就取它
- 否则，检查两个可能的选择，在游戏结束时为第二个玩家选择一个结果较低的选项
因此，第一个玩家的最优和是序列中所有数字的和减去第二个玩家将得到的最小和。公式如下：
p(i，j(=Ai (如果i=j(
p(i，j(=Ai+Ai+1+…+Aj-min｛p(i+1，j(，p(i，j-1(｝ (如果j>i(
我们使用相同的公式来计算第二个玩家和第一个玩家的和，因为第二个游戏玩家也想得到最大可能值。
其正确性可以很容易地归纳证明。此外，我们可以从中获得动态编程解决方案：首先计算每个对(i，j(的p(i，j(的值，并将其保存在表nxn中。解取O(n^3(。此外，还有一种方法可以对和A1+Ai+1+Ai+2+…+进行预处理Aj：我们可以计算和A1+…+对于每个j，每次应用公式p(i，j(时，Aj可以使用sum(1，j(-sum(1，i(，这样解将取O(n^2(。
有更快的算法吗？在我的解决方案中，我得到了一系列的选择，这些选择为第一个玩家提供了最大的总和，但它太"强"了：我被要求得到一系列能给他带来胜利的选择，而不管最终总和是最大的。因此，毫无疑问，我执行了一些不必要的步骤。
更好的解决方案似乎是贪婪算法，因为我见过同样的问题，但序列中有偶数个数字(这里https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450)。
有人能给我一些关于贪婪的解决方案应该是什么样子的想法或线索吗？提前谢谢！
"贪婪"是一个简单的概念：与其查看整个游戏树，不如只考虑最大化当前级别的短期结果。在这种情况下，这意味着采用两个可用元素中较大的一个，而根本不使用递归。
您的完整解决方案，最大化收到的金额，有效；对于一般情况来说，这有点过头了。
两者之间的平衡可能是有用的，这是一种前瞻一定数量移动的启发式方法。例如，只提前四步(每个玩家两步(玩游戏，然后选择一个能最大化你的差距的。
Greedy解决方案意味着算法在每一步都选择最佳的局部选项。在您的情况下，最佳局部选项意味着在第一个元素和最后一个元素之间选择最大值。
关于贪婪算法的几点思考
优点
-
实现很简单
-
O(n(复杂度时间
缺点
-
算法可能陷入局部最小
-
最佳局部步长并不总是最佳全局步长，因此最终结果并不总是最佳可能结果