As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center用于指导。
这个问题是在一次采访中问我的，它尴尬地暴露了我在动态编程方面的缺点。如果有人能帮我破解这个，我将不胜感激。另外，如果你能在设计解决方案的过程中解释你的思维过程，这对我（和其他人）将是非常有帮助的，因为当我看到一个使用动态编程范式但难以提出自己的解决方案时，我似乎能够理解。
不费吹灰之力，这是我被问到的问题。
给定一个整数i并设置X点k，x1，…x2在实线上，使用动态编程从集合中选择xk点，以最小化从i中的每个点到X中的某个点的距离之和。
最佳答案
对于大多数dp问题，我试图找到一种归约关系。也就是说，我可以在每一步中减少问题的大小（比如分而治之，但通常不划分问题，它只是去掉一小部分）。在这个问题上（和许多其他问题一样），我们可以做一个非常简单的观察：要么第一个点在i点的集合中，要么不是。
一些符号：假设x={x1，x2，…，xk}，并表示约化集xn={xn，xn+1，…，xk}。
所以观察结果是x1是i点之一，或者不是。让我们调用i集合查找函数msd（i，xk）（最小距离和）。我们可以将这一切掉的观察表述如下：
msd（i，xk）=msd（i-1，xk-1）u{x1}或msd（i，xk-1）
我们可以通过实现一种简单的方法来确定“非此即彼”部分的形式，即检查这两个选项中的哪一个是真的：我们遍历集合x并计算距离之和，然后检查哪一个是真的更小的。在这一点上，我们注意到，该检查的运行时间为ki，因为我们将天真地运行每个k点，并获取与大小i集中的点之间的最小距离。
我们对基本情况作了两个简单的观察：
msd（i，xi）=xi
MSD（0，xn）={}
首先，当我们在一组大小的点中寻找i点时，我们显然只需要整个点集。
第二个是当在一个集合中找不到点时，我们返回空集合。这种归纳确保msd返回大小为i的集合（对于i的情况是这样的，根据我们对msd的上述定义，通过归纳是正确的）。
就这样。会找到合适的集合。
运行时复杂度是由上界上界，在这里，步骤是我们从上面检查的cc。这是因为msd将在i=0和x1-xk（总共O(ik * step)个可能参数）范围内的参数上运行。
这使得我们的运行时间为o（（ik）2）。
下面的部分是基于我对OP问题的理解。我不确定x中每个点到i大小的子集的距离是每个点到子集中每个其他点的距离之和，还是x中每个点到子集本身的距离之和。
即x的sigma in x of（x到子集中每个点的距离之和）或x的sigma in x of（x到子集的距离，即x到子集中任何点的最小距离）
我想是后者。
我们可以通过优化上面的O(ik)检查来减少运行时间。我们注意到元素实际上是被排序的（尽管在当前的符号中是以相反的顺序排列的），因为当我们在上面添加它们时，我们总是从右边开始这样做。假设它们是从一开始就被排序的，那么它们将一次退出msd例程。如果一开始没有分类，我们就可以对它们进行分类，无论如何，这只会花费0-i的费用。
排序后，检查每个点与集合中某个点的距离将ik，因为我们对每个点执行二进制搜索。这将产生O(ik)的总运行时间。
=o（k2*ilogi）。
最后，我们可以用o（k3logk）来表示。不是最快的解决方案，而是一个解决方案。
我相信会有更多的优化，但那是我的2c。
关于algorithm - 面试中的动态编程算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7631180/