<分区>
我在寻找问题的最佳动态规划解决方案时遇到困难，非常感谢任何帮助。最优解为O(T^2+M)；我只能找到 O(NM^2) 的解决方案。 问题是:
有 N 个标记为 1,2...N 的储物柜。每个储物柜都上锁，但可以使用其唯一的 key 打开。每个储物柜的 key 副本都在其相邻的储物柜中；即储物柜 i 的 key 副本放在储物柜 i+1 和 i-1 中(储物柜 1 的 key 仅在储物柜 2 中，储物柜 N 的 key 仅在储物柜 N-1 中)
T 个网球在 T 个不同的储物柜中(你知道它们在哪个储物柜中)。您获得了 M 个储物柜的 key ，您的目标是通过打开最少数量的储物柜来收集所有网球。
我给出的唯一提示是: 提示:你能否有效地判断第 i 个和第 j 个储物柜之间是否至少存在一个网球？
最佳答案
首先在 N + 1 处放置一个带有 key 但没有网球的虚拟单元格。
现在从第二个键开始，一直进行到最后一个键(您应该注意，它是一个虚拟键)。
在每次迭代中，针对两种情况计算当前键左侧(含)的网球的最优解:a。使用当前 key ，和 b。当前 key 未被使用。最优解还应该记录实际使用的最右边的key。
如果当前键没有被使用，则使用之前最好的两个方案来更新成本，使用最右边实际用于覆盖当前键左侧(含)球的键。如果使用当前 key ，则对于当前 key 左侧(含)的每个球，计算从该 key 或之前使用的 key (取决于 key 之间的中点)打开是否值得。
整体解决方案是在虚拟 N + 1 单元格处的解决方案，并且不使用其中的 key 。
关于algorithm - 动态编程 : Tennis Balls, 储物柜和 key ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34869244/