Closed. This question needs to be more focused。它当前不接受答案。
想改善这个问题吗？更新问题，使其仅关注editing this post一个问题。
4年前关闭。
Improve this question
我在寻找问题的最佳动态编程解决方案时遇到了麻烦，非常感谢您的帮助。最优解为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个储物柜之间是否至少存在一个网球？
想改善这个问题吗？更新问题，使其仅关注editing this post一个问题。
4年前关闭。
Improve this question
我在寻找问题的最佳动态编程解决方案时遇到了麻烦，非常感谢您的帮助。最优解为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 和一个网球。
现在从第二个键开始，一直进行到最后一个键(您应该注意，这是一个虚拟键)。
在每次迭代时，针对两种情况，计算当前键左侧(含)的网球的最佳解:使用当前密钥，并且b。当前密钥未使用。最佳解决方案还应该记录实际使用的最右边的密钥。
如果未使用当前键，则使用以前的最佳两种解决方案来更新成本，方法是使用实际用于覆盖当前键左侧(包括此端)的球的最右边的键。如果使用了当前键，则对于当前键左侧(包括此键)左侧的每个球，计算从该键还是从先前使用的键打开是否值得(取决于键之间的中点)。
整体解决方案是位于虚拟N + 1单元中且不使用其中密钥的解决方案。
10-07 23:28