有一个N整数（N <5×10 ^ 5）的数组，有两个玩家（A和B）正在按顺序删除该数组的元素。 A试图让最后一个数字变大，B试图缩小。
*两个玩家只能删除第一个元素或最后一个元素。 * A首先开始删除。
我们说吧; A = [3,100,4,50]
-A将删除50因为如果A删除3则B可以删除100不是A想要的东西。
我通过使用动态编程解决了这个问题，但问题是内存。我使用2D整数数组进行记忆，当我收到一个大小为10 ^ 5的数组时，它消耗了大量的内存（对于这种情况，10 ^ 5x10 ^ 5x2 = 2x10 ^ 10字节，这是18.6千兆字节。）但我想要用最多512 MB的内存来解决这个问题。我的问题是“解决这个问题的空间效率更高的方法是什么？”。
实际上，我认为你不需要动态编程。答案永远是中间的元素，如果N是偶数，答案是两个中间元素中的最大值。这是证明：
假设您是玩家A，并且您希望剩余的元素大于中间元素。如果元素位于数组的右半部分，您肯定会从数组的开头开始获取元素（尽可能长时间保留您想要的元素）。现在想想玩家B将如何反应，为什么他会帮助你实现目标？！当然玩家B将开始从数组的末尾获取元素以摆脱你想要的大元素。
如果你是玩家B同样的事情，并且你试图保持一个小于中间元素的元素，玩家A将开始从另一侧获取元素以移除你想要的小元素。
如果大小元素都在数组的同一侧，则两个玩家都可以计算出他们是否可以拥有他们想要的元素。如果其中一个人无法得到他想要的元素，他会推动另一个玩家保持中间元素，因为总是移除另一边的元素。
唯一的特殊情况是如果N是偶数，在这种情况下，最后一步将由玩家A完成，并且数组将剩下2个元素（这是中间的两个元素）。在这种情况下，玩家A肯定会移除较小的元素并保留较大的元素。
假设您计算所有长度k阵列的最佳分数（k将从1开始并逐渐增加）并且同时选择第一个玩家。
您可以从长度为k的阵列计算所有长度k + 1阵列的最佳分数（通过考虑删除第一个或最后一个元素并选择最佳元素）。
因此，您可以通过保留此数组的两个副本（k和k + 1）并丢弃所有较小的长度来使用O（N）内存执行此操作。
换句话说，如果将结果存储在大小为[2] [N]的二维数组中，则可以将长度k数组的结果存储在位置k％2（将为0或1）中。
这让我想起了alpha-beta修剪（https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning）。 A / B修剪适用于你有两个玩家竞争游戏并且你可以为游戏的每个动作分配一个分数的情况，例如国际象棋或西洋跳棋，但这应该同样有效。
问题归结为对可能的游戏状态和分数的树搜索，在这种情况下，对于每个状态，玩家之间的差异分数。 A / B修剪允许根据对方玩家的预期得分减少搜索空间，切断整个子树。这个想法是，不需要考虑导致对方玩家得分高于你自己预期得分的子树。