剩余的最后一个数（动态规划）

Question

剩余的最后一个数（动态规划）

algorithmdynamic-programminggame-theory

3

有一个包含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吉字节）。但是我希望以最多512 mb的内存解决此问题。我的问题是“解决此问题的更有效的空间利用率方法是什么？”。

- M.Soyturk

一个小提示：将内存消耗从O(N^2)降至O(N)可能并没有帮助，只要时间仍然是O(N^2)。对于N=1,000,000，平方是10^{12}，因此解决问题的单个实例可能需要几个小时。 - Gassa

@Gassa 我现在不担心时间复杂度的问题，我关注的是空间复杂度。 - M.Soyturk

@Gassa 但我需要稍后考虑。你有解决时间复杂度问题的建议吗？ - M.Soyturk

我会从以下问题开始。假设有n个元素，A [1]，...，A [n]，玩家A希望数字A [i]保持最后一个，玩家B想要阻止它，他们都知道目标索引i。对于哪个i，玩家B可以阻止他们，哪个i他们无法阻止？ - Gassa

下一个问题如下。假设 n = 100，数字 A [33] 和 A [66] 是大数，而其他数字都很小。玩家 A 是否能够获得其中一个大数作为最后剩下的数？ - Gassa

3个回答

4

假设您计算了所有长度为k的数组（k将从1逐渐增加），并且使用了第一个玩家的两种选择，以获得最佳分数。

您可以仅通过考虑删除第一个或最后一个元素并选择最佳元素，就可以从长度为k的数组中计算出所有长度为k+1的数组的最佳分数。

因此，您可以通过仅保留两个副本（k和k+1）的数组来使用O(N)内存来完成此操作，并且丢弃所有较小的长度。

换句话说，如果您将结果存储在大小为[2][N]的二维数组中，则可以将长度为k的数组的结果存储在位置k％2中（它将是0或1）。

- Peter de Rivaz

不错的回答。我认为值得注意的是，这种方法被称为滚动表技术。 - Said A. Sryheni

1

这让我想起了alpha-beta剪枝（https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning）。A/B剪枝适用于你有一个两个玩家的竞技游戏并且你可以为每个游戏动作分配一个分数的情况，例如象棋或跳棋，但这同样适用。

问题归结为对可能的游戏状态和得分进行树形搜索，这种情况下是玩家之间的差分得分。A/B剪枝允许减少搜索空间，基于对手的期望得分，整个子树被切断。其思想是不需要考虑导致对手得分高于你自己期望得分的子树。

- Matti Lyra

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Said A. Sryheni · Accepted Answer

实际上，我认为您在这里不需要动态规划。答案将始终是中间的元素，在情况下，如果N是偶数，则答案是两个中间元素中的最大值。这是证明：

假设您是玩家A，并且您希望剩余的元素大于中间元素。如果元素在数组的右半部分，则您肯定会从数组的开头开始取元素（尽可能地保留您希望的元素）。现在想想玩家B会如何反应，他为什么要帮助您实现目标？当然，玩家B会开始从数组的末尾取元素，以摆脱您所期望的大元素。

如果您是玩家B，并且您正在尝试保留一个小于中间元素的元素，那么玩家A将从另一侧开始取元素，以删除您所期望的小元素。

如果大和小元素都在数组的同一侧，则两个玩家都可以计算出它们是否可以拥有他们所希望的元素。如果其中一个人无法获得他想要的元素，他将通过始终删除另一侧的元素来推动另一个玩家确保保留中间元素。

唯一的特殊情况是如果N是偶数，在这种情况下，最后一步将由玩家A完成，并且数组将剩下2个元素（即中间的两个元素）。在这种情况下，玩家A肯定会删除较小的元素并保留较大的元素。