use*_*078 15 algorithm dynamic-programming
我在一次采访中向我询问了这个问题,并且令人尴尬地暴露了我在动态编程方面的缺点.如果有人可以帮我解决这个问题,我将不胜感激.此外,如果您能够在设计解决方案时解释您的思维过程对我(以及其他人)非常有帮助,因为当我看到一个使用动态编程范例的解决方案但我很难理解时,我似乎能够理解跟我一起.
不用多说,这是我被问到的问题.
给定一个整数i,并设置X的k点x1,x2,... xk上实线,选择i从设定点X,以尽量减少对距离的每一个点的总和X到一个点在i使用动态规划.
对于大多数DP问题,我尝试找到一种减少与征服的关系.也就是说,我可以通过每一步切断问题大小的关系(如分而治之,但通常不会分解问题,只是删除了一小部分).在这个问题中(和许多其他问题一样)我们可以做一个非常简单的观察:第一个点在点集中i,或者它不是.
一些表示法:假设X = {x 1,x 2,...,x k },并且表示简化集合X n = {x n,x n + 1,...,x k }.
因此,观察结果是x 1是其中一个i点,或者不是.让我们调用我们的i-set寻找函数MSD(i,X k)(最小距离之和).我们可以表达如下切割观察:
MSD(i,X k)= MSD(i-1,X k-1)U {x 1 }或MSD(i,X k-1)
我们可以通过实现一种简单的方法来检查"两个或两个"部分,它实际上是检查这两个选项中的哪一个:我们遍历集合X并计算距离之和,并检查哪个实际上更小.我们在这一点上注意到,该检查具有运行时间,ki因为我们将天真地遍历每个k点并从该组大小中的点获取最小距离i.
我们对基本案例做了两个简单的观察:
MSD(i,X i)= X i
MSD(0,X n)= {}
首先,在寻找i一组尺寸的点时,i我们显然只需要整套.
第二个是当在集合中寻找没有点时,我们返回空集.这可以有效地确保MSD返回大小的集合i(对于i=0根据我们上面的MSD定义,感应为真的情况,这是正确的).
而已.那将找到合适的集合.运行时复杂性的上限取决于O(ik * step)我们O(ik)从上面检查的步骤.这是因为MSD将在范围为0-i和X 1 - X k的参数上运行,这是ik可能的参数.
这使我们的运行时间为O((ik)2).
以下部分基于我对OP问题的理解.我不确定X中每个点与i大小子集的距离是否是每个点与子集中每个其他点的距离之和,或X中每个点与子集的距离之和本身.
即x中x的西格玛(子集中每个点的x距离之和)或X中x的西格玛(距离子集x的距离,即从x到子集中任何点的最小距离)
我假设后者.
我们可以通过优化O(ik)上面的检查来减少运行时间.我们注意到元素实际上是排序的(虽然在当前符号中是相反的顺序),因为当我们添加它们时,我们总是从右侧进行.假设它们已经开始排序,它们将一次退出MSD例程.如果他们没有排序开始我们可以对它们进行排序,这只会花费O(klogk).
一旦排序,检查每个点与集合中的点的距离将是k * logi因为对于每个点我们进行二分搜索.这产生总运行时间O(ik * klogi + klogk)
= O(k 2*ilogi).
最后,我们可以表示为O(k 3 logk).不是最快的解决方案,而是解决方案.
我确信还有更多的优化,但这是我的2c.