最后剩下的数字（动态规划）
The Last Remained Number (Dynamic Programming)
有一个包含 N 个整数（N < 5x10^5）的数组，并且有两个玩家（A 和 B）依次删除这个数组的元素。 A 试图使最后剩下的数字变大，而 B 试图变小。
*双方玩家只能删除第一个元素或最后一个元素。
*A先开始删除。
假设； A = [3,100,4,50]
-A 将删除 50，因为如果 A 删除 3，那么 B 可以删除 100，这不是 A 想要的。
我已经用动态规划解决了这个问题，但问题是内存。我使用二维整数数组进行记忆，当我收到一个大小为 10^5 的数组时，它会消耗大量内存（对于这种情况，10^5x10^5x2 = 2x10^10 字节，即 18.6 GB。）但我想要最多用 512 MB 内存解决这个问题。我的问题是 "what would be the more space efficient way to solve this problem?"。
假设您计算所有长度为 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-pruning 适用于您有两人竞技游戏的情况 并且 您可以为游戏的每一步分配一个分数，例如国际象棋或西洋跳棋，但这应该有效同样好
问题归结为对可能的游戏状态和分数进行树搜索，在这种情况下，对于每个状态，玩家之间的差异分数。 A/B-pruning 允许减少搜索 space，根据 opposing 玩家的预期得分，切断整个子树。这个想法是不需要考虑导致对方玩家得分高于您自己的预期得分的子树。
其实我觉得这里不需要动态规划。答案永远是中间的元素，如果 N 是偶数，答案就是中间两个元素中的最大值。证明如下：
假设您是玩家A，您希望剩余的元素大于中间的元素。如果该元素位于数组的右半部分，您肯定会从数组的开头开始获取元素（尽可能长时间保留您想要的元素）。现在想想玩家B会有什么反应，他为什么要帮你达成目标？！当然玩家 B 将开始从数组的末尾获取元素以摆脱你想要的大元素。
如果您是玩家 B，并且您试图保留一个小于中间元素的元素，玩家 A[=30]，也会发生同样的事情=] 将开始从另一侧取元素以删除您想要的小元素。
如果大元素和小元素都在数组的同一边，则双方玩家可以计算是否可以得到他们想要的元素。如果他们中的一个不能得到他想要的元素，他将通过始终移除另一侧的元素来推动另一个玩家确保保持中间元素。
唯一的特殊情况是如果 N 是偶数，在这种情况下最后一步将由玩家 A 完成，并且数组将剩下 2 个元素（中间的两个元素）。在这种情况下，玩家 A 肯定会移除较小的元素并保留较大的元素。
有一个包含 N 个整数（N < 5x10^5）的数组，并且有两个玩家（A 和 B）依次删除这个数组的元素。 A 试图使最后剩下的数字变大，而 B 试图变小。
*双方玩家只能删除第一个元素或最后一个元素。 *A先开始删除。
假设； A = [3,100,4,50]
-A 将删除 50，因为如果 A 删除 3，那么 B 可以删除 100，这不是 A 想要的。
我已经用动态规划解决了这个问题，但问题是内存。我使用二维整数数组进行记忆，当我收到一个大小为 10^5 的数组时，它会消耗大量内存（对于这种情况，10^5x10^5x2 = 2x10^10 字节，即 18.6 GB。）但我想要最多用 512 MB 内存解决这个问题。我的问题是 "what would be the more space efficient way to solve this problem?"。
假设您计算所有长度为 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-pruning 适用于您有两人竞技游戏的情况 并且 您可以为游戏的每一步分配一个分数，例如国际象棋或西洋跳棋，但这应该有效同样好
问题归结为对可能的游戏状态和分数进行树搜索，在这种情况下，对于每个状态，玩家之间的差异分数。 A/B-pruning 允许减少搜索 space，根据 opposing 玩家的预期得分，切断整个子树。这个想法是不需要考虑导致对方玩家得分高于您自己的预期得分的子树。
其实我觉得这里不需要动态规划。答案永远是中间的元素，如果 N 是偶数，答案就是中间两个元素中的最大值。证明如下：
假设您是玩家A，您希望剩余的元素大于中间的元素。如果该元素位于数组的右半部分，您肯定会从数组的开头开始获取元素（尽可能长时间保留您想要的元素）。现在想想玩家B会有什么反应，他为什么要帮你达成目标？！当然玩家 B 将开始从数组的末尾获取元素以摆脱你想要的大元素。
如果您是玩家 B，并且您试图保留一个小于中间元素的元素，玩家 A[=30]，也会发生同样的事情=] 将开始从另一侧取元素以删除您想要的小元素。
如果大元素和小元素都在数组的同一边，则双方玩家可以计算是否可以得到他们想要的元素。如果他们中的一个不能得到他想要的元素，他将通过始终移除另一侧的元素来推动另一个玩家确保保持中间元素。
唯一的特殊情况是如果 N 是偶数，在这种情况下最后一步将由玩家 A 完成，并且数组将剩下 2 个元素（中间的两个元素）。在这种情况下，玩家 A 肯定会移除较小的元素并保留较大的元素。