algorithm - 猜谜游戏加权最佳猜测

Question

我在实习面试中遇到了以下问题，我仍然想知道最好的解决方案是什么。

问题:

假设您正在玩猜谜游戏。您可以猜出 1 到 n 之间的一个数字，并且您有一个 API 可以告诉您数字是大还是小。

现在假设每个猜测都是加权的(即你猜 20，所以成本是 20)

创建一个算法来找到最小化成本的最佳第一次猜测。

我在想什么:

在问题的正常版本(没有权重)中，解决方案是简单的二分查找。

但是，在这种情况下，我认为我需要对所有可能的猜测序列执行平均案例分析，这会增加解决方案的复杂性。例如，我从猜测 20 开始，所以我将数字为 20 的成本包括在内，然后通过在较小的空间上执行类似的操作来找到下一个最佳猜测(假定我不再猜测 20)。我对所有第一次猜测都执行此操作，然后取最小值。

如有任何帮助，我们将不胜感激。

Answer 1

我认为这是一个动态规划问题，您最终会计算出所有区间 [i, j] 的最佳成本的成本，其中 1 <= i <= j <= 20。

对于 i=j，猜测 {i} 的成本是 i。

要找到区间 [i, j] 的最佳猜测成本，您需要考虑 i <= k <= j 的所有可能猜测 k。使用猜测 k 的总成本是 k + p * [i, k-1] 的最佳成本 + q * [k+1, j] 的最佳成本。 (当 i > j 时，[i, j] 的成本为 0)。假设您要平均成本，那么 p 将是 (k - i)/(j + 1 - i) 并且 q 将是 (j - k)/(j + 1 - i) 这些应该是目标的概率在 [i, k - 1] 和 [k + 1, j] 中。

您从大小为 1 的所有区间的最佳成本开始。您可以根据这些计算大小为 2 的所有区间的最佳成本，然后继续计算大小为 20 的所有区间的最佳成本。然后，您通常会回溯找出每个阶段的所有最佳决策，可能会使用您在计算成本时存储的信息。但在你的情况下，你只需要知道最好的第一个猜测，所以你可以在计算时存储它。

对于 N=20，您有 O(N^2) 个最佳成本需要计算，每个成本不超过 O(N) 个工作量，因此我们有一个 O(N^3) 个算法。不是很好，但完全不像指数，而且对于 N=20 来说完全可以负担​​得起。