动态规划:网球球、储物柜和钥匙

Question

我很难找到一个问题的最佳动态规划解决方案，并将非常感谢任何帮助。最优解是O(T^2+M)，我只能找到O(NM^2)的解。问题是：

有N个储物柜标有1，2.N.每个储物柜都是锁着的，但可以用它的唯一键打开。每个储物柜的钥匙副本都在其相邻的储物柜中；也就是说，一个锁柜钥匙的副本放在储物柜i+1和i-1中(储物柜1的钥匙只在储物柜2，而锁柜的钥匙N只在储物柜N-1)。

网球在T个不同的储物柜里(你知道他们在哪个储物柜里)。给你钥匙M的储物柜和你的目标是收集所有的网球通过打开最少的储物柜。

我给出的唯一提示是:你能有效地判断第一和jth储物柜之间是否至少存在一个网球吗？

Answer 1

首先，用钥匙在N+1处放置一个虚拟细胞，而不使用网球。

现在从第二个键开始，继续到最后一个键(您应该注意，这是一个虚拟键)。

在每次迭代时，计算当前键左侧网球的最优解(包括两种情况)：a使用当前键，b不使用当前键。最优解还应记录实际使用的最右边键。

如果不使用当前键，则使用前面最好的两个解决方案来更新成本，使用最右边的键实际用于覆盖当前键左侧的球(包括)。如果使用当前键，那么对于当前键左侧的每个球(包括在内)，计算从该键打开还是从以前使用的键打开(取决于键之间的中点)。

整体解决方案是在虚拟N+1单元上，而不是在其中使用键。