数字选择游戏的贪心算法
Greedy algorithm on a number choice game
问题给出如下：
有一个游戏有 n 个数字 (a1, a2, a3,..,an) 和两个玩家。玩家从序列中取出数字；在每一轮中，玩家都可以选择序列中的第一个或最后一个数字。当序列为空时，总和较大的玩家获胜；如果相等，则平局。
目标是编写一个算法，returns 一系列选择以保证第一个玩家获得最佳结果（获胜或平局），假设第二个玩家将发挥最佳效果。
我想出了一个递归公式，可以转化为动态规划解决方案：
- 对于序列 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）的值并将其保存在table nxn中。该解决方案需要 O(n^3)。此外，还有一种方法可以对总和 A1 + Ai+1 +Ai+2 +...+ Aj 进行预处理：我们可以计算每个 j 的总和 A1 +...+ Aj 并且每次应用公式 p (i,j) 可以使用 sum(1,j) - sum(1,i) 以便解决方案需要 O(n^2).
有没有更快的算法？在我的解决方案中，我得到了为第一个玩家提供最大总和的选择序列，但它也是 "strong"：我被要求获得一系列能够给他带来胜利的选择，而不考虑最大化最终和。所以，毫无疑问，我执行了一些不必要的步骤。
更好的解决方案似乎是贪心算法，因为我见过同样的问题，但是序列中的数字是偶数（这里是https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450）。
任何人都可以给我一些关于贪婪解决方案应该是什么样子的想法或线索吗？提前致谢！
贪心解意味着算法在每一步都选择最佳局部选项。在您的情况下，最佳本地选项意味着在第一个元素和最后一个元素之间选择最大值。
关于贪心算法的一些思考
优点
易于实施
O(n)复杂度时间
缺点
算法可能卡在局部最小值
最佳局部步骤并不总是最佳全局步骤，因此最终结果并不总是最佳结果
"Greedy" 是一个简单的概念：与其查看整个游戏树，不如只考虑最大化当前级别的短期结果。在这种情况下，这意味着取两个可用元素中较大的一个，并且根本不使用递归。
您的完整解决方案，最大化收到的总和，有效；对于一般情况来说，这只是有点矫枉过正。
两者之间的平衡可能会有用，这是一种可以预见一定步数的启发式方法。例如，在游戏中只提前四步（每位玩家两步），然后选择使您的差异最大化的一步。
问题给出如下：
有一个游戏有 n 个数字 (a1, a2, a3,..,an) 和两个玩家。玩家从序列中取出数字；在每一轮中，玩家都可以选择序列中的第一个或最后一个数字。当序列为空时，总和较大的玩家获胜；如果相等，则平局。
目标是编写一个算法，returns 一系列选择以保证第一个玩家获得最佳结果（获胜或平局），假设第二个玩家将发挥最佳效果。
我想出了一个递归公式，可以转化为动态规划解决方案：
- 对于序列 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）的值并将其保存在table nxn中。该解决方案需要 O(n^3)。此外，还有一种方法可以对总和 A1 + Ai+1 +Ai+2 +...+ Aj 进行预处理：我们可以计算每个 j 的总和 A1 +...+ Aj 并且每次应用公式 p (i,j) 可以使用 sum(1,j) - sum(1,i) 以便解决方案需要 O(n^2).
有没有更快的算法？在我的解决方案中，我得到了为第一个玩家提供最大总和的选择序列，但它也是 "strong"：我被要求获得一系列能够给他带来胜利的选择，而不考虑最大化最终和。所以，毫无疑问，我执行了一些不必要的步骤。
更好的解决方案似乎是贪心算法，因为我见过同样的问题，但是序列中的数字是偶数（这里是https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450）。
任何人都可以给我一些关于贪婪解决方案应该是什么样子的想法或线索吗？提前致谢！
贪心解意味着算法在每一步都选择最佳局部选项。在您的情况下，最佳本地选项意味着在第一个元素和最后一个元素之间选择最大值。
关于贪心算法的一些思考
优点
易于实施
O(n)复杂度时间
缺点
算法可能卡在局部最小值
最佳局部步骤并不总是最佳全局步骤，因此最终结果并不总是最佳结果
"Greedy" 是一个简单的概念：与其查看整个游戏树，不如只考虑最大化当前级别的短期结果。在这种情况下，这意味着取两个可用元素中较大的一个，并且根本不使用递归。
您的完整解决方案，最大化收到的总和，有效；对于一般情况来说，这只是有点矫枉过正。
两者之间的平衡可能会有用，这是一种可以预见一定步数的启发式方法。例如，在游戏中只提前四步（每位玩家两步），然后选择使您的差异最大化的一步。