D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m)
其中q的范围从j-1到m-1，Cost等于中位数绝对距离之和。使用天真的O(n) Cost实现，会导致整个问题的O(n^3k) DP解决方案。然而，由于可以在恒定时间内更新成本，而不是每次都从头计算，因此可以将其改进为O(n^2k)，利用排序序列的事实：
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1 if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1 if h is even
更多细节请参见报告。除了成本函数的更新不同之外，k-medians的实现与k-means相同。 http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf
据我所知，问题是：
我们在一条线上有n个点。 我们想在该线上放置k个位置。我称它们为目的地。 将每个n个点移动到k个目的地中的一个，使距离之和最小。我称这个总和为总成本。 目的地可以重叠。
一个显而易见的事实是，对于每个点，我们应该寻找左侧和右侧最近的目的地，并选择最近的一个。
另一个重要的事实是，所有目的地都应该在点上。因为我们可以将它们向左或向右移动到达一个点，而不增加总距离。
根据这些事实，考虑以下DP解决方案：
DP [i] [j]表示前i个点所需的最小总成本，当我们只能使用j个目的地时，并且必须在第i个点上放置一个目的地。
要计算DP [i] [j]，请先确定第i个点之前的目的地（我们有i个选择），并针对每个选择（例如第k个点）计算添加新点（第k个点）后所需的点之间的距离。将其与DP [k] [j-1]相加，并找到所有k的最小值。
初始状态（例如j = 1）和最终答案的计算留作练习！
任务0 - 将对象的位置按非递减顺序排序
我们定义'center'为对象的位置，它被移动到的位置。
现在我们有两个观察结果;
对于N个位置，“中心”将是最接近这些N个位置平均值的位置。例如，让1、3、6、10成为位置。那么平均值=5。最近的位置是6。因此，这些元素的中心是6。当所有元素需要分组为1组时，这给出了移动成本最小的位置。
将N个位置“最优地”分组为K组。当添加第N+1个对象时，它只会干扰第K个组，即前K-1个组将保持不变。
从这些观察结果中，我们建立了一种动态编程方法。
Let Cost[i][k] and Center[i][k] be two 2D arrays.
Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups
Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed.
设{ L }是从i-L、i-L+1、..i-1中具有相同中心的元素。
(Center[i-L][k] = Center[i-L+1][k] = ... = Center[i-1][k])
这些是计算第i个元素时需要考虑的唯一对象(来自观察2)
现在
Cost[i][k] will be
min(Cost[i-1][k-1] , Cost[i-L-1][k-1] + computecost(i-L, i-L+1, ... ,i))
Update Center[i-L ... i][k]
通过观察1，可以轻松地找到computecost()的中心。
时间复杂度：
Sorting O(NlogN)
Total Cost Computation Matrix = Total elements * Computecost = O(NK * N)
Total = O(NlogN + N*NK) = O(N*NK)
让我们看一下k=1。
对于k=1且n为奇数，所有点都应该移动到中心点。对于k=1且n为偶数，所有点都应该移动到中心点之一或它们之间的任何位置。我所说的“中心”是指在两侧点数方面的中位数。
你可以看到这一点，因为如果你选择一个目标点x，它右边的点比左边的点多，那么向右移动一个新的目标点1会导致成本降低（除非右边恰好比左边多一个点且目标点是一个点，在这种情况下n为偶数且目标点在/在两个中心点之间）。
如果你的点已经排序，这是一个O(1)操作。如果没有，我认为它是O(n)（通过一个顺序统计算法）。
一旦你找到了所有点都要移动到的位置，找到成本就是O(n)。
因此，无论点是否排序，这都是O(n)。