如何使用动态规划解决问题

Question

蜘蛛侠陷入困境

超凡蜘蛛侠想要在与电光人战斗之前为自己创造出蜘蛛网流体。他最初有 1 毫升 幅面流体。蜘蛛侠想要创造N毫升 幅面流体。所以他可以用 3 种不同的方式改变液体量 -:

1. 将液体量加倍（成本为 x）。
2. 增加液体 1 毫升（成本为 y） .
3. 减少液体 1 毫升（成本为 z） .

现在，上述所有操作都有不同的相关成本 分别进行上述操作。帮助蜘蛛侠找到生成的最低成本 N ml 液体起始于 1 毫升液体。 注意：您需要准确生成 网络流体。

任何解决问题的线索都值得赞赏。尝试了动态编程方法，但无法正常工作。

Answer 1

因此，如果 log(2, N) 是自然数，那么您可以通过支付 x * log(2, N) 的成本来达到您想要的效果，复制流体直到达到您需要的确切数量。但您可能能够最小化达到该值的成本，因为，例如，如果 y < x, then the first duplication is equivalent to adding 1ml to the already existent 1ml.

因此，在我们的场景中，您需要通过重复 y 成本来“积累”，直到 y * 2^k > x

其中 2^k 是您迄今为止实现的价值并且您寻求加倍。从那时起，您将重复 x 的成本，直到达到 log(2, N)。我们仍然假设我们有 2 的精确幂，因为一旦您了解了这种情况，就很容易调整，因此该解决方案将适用于您需要达到不是 2 的精确幂的值的情况。

因此，构建阶段如下所示：

cost <- 0

while k < log(2, N)
    cost <- min(k * y, x)
    k <- k * 2
end while

很好，不是吗？

现在，让我们调整我们的解决方案，请注意，当且仅当 N 不是 2 的精确幂时，该调整才适用。让我们仅进行累积，直到 log(2, N - 1) 向下舍入。

现在，计算：

x + z * (2N - 2 * 当前(k))

和

y *（当前（k）-N）

获取最终成本，无论您是否需要进行最终加倍并反复递减，还是最好增加它直到达到所需值。

这些想法应该可以帮助你开始，实际的实施取决于你。