中位选址的动态规划

Question

我被困在这个问题上，想知道是否有人可以帮助我:在x轴上有n个房子{x_1，x_2，...x_n}，我需要找到x轴上的位置，给出房子和位置之间的最小距离和。

这当然是微不足道的，但我也需要能够在O(n)时间内完成它，并且我被动态算法卡住了。

编辑:显然，它不需要是DP算法，正如我所说的，这使得它变得微不足道，很抱歉造成了混乱，感谢您的回复。

Answer 1

我相当了解中位数查找，也非常了解动态编程，但我不知道任何可以合理地理解为DP的中位数查找算法。

如果你的x被排序，并且你不知道中位数是答案，我可以看到从给定索引的右侧和左侧计算部分和作为DP-ish子问题。然后，最优解最小化左右部分和的和。

但当然，我非常不喜欢说“用Y解决X”的问题，特别是当Y不是真的适合的时候。“解决X，你可能想要考虑使用Y"，是一个更好的问题形式。