首先回顾一个引理。一条直线上有若干个点p0,p1,...pn，其median位置处的点是pm，那么该点满足最小化sum{abs(pi-p)}, for i=0,1,...,n
在本题中，我们定义dp[i][k]表示前i个房子的范围内设置k个邮局（或者说设置k个邮局覆盖前i个房子），所得到的最小的objective。我们考虑，那么k-1个邮局可以覆盖多少房子？假设是j个房子。于是我们有一种可能，只要j取得合适，前j个房子被前k-1个邮局覆盖是最优的，并且第j+1到第i个房子被第k个邮局覆盖是最优的。于是就有
dp[i][k] = dp[j][k-1] + range[j+1][i]。其中range[j+1][i]表示区间[j+1,i]内的房子被1个邮局覆盖的objective.显然这1个邮局是位于[j+1,i]的中位数位置，并且range[j+1][i]是可以提前计算出来的。
怎么找到这个合适的j呢？我们可以把所有的j的可能都遍历一遍，最小的dp[j][k-1] + range[j+1][i]就对应着最合适的j。也就是说，不合适的j计算出来的dp[j][k-1] + range[j+1][i]都会偏大，从而不会被dp[i][k]采纳。为什么呢？
举个例子，我们查看某个j。dp[j][k-1]给出了一个k-1个邮局覆盖前j个房子的最优解。range[j+1][i]给出了后面几个房子被1个邮局覆盖的最优解。但是统一来看所有的k个邮局，可能第j个房子更适合被第k个邮局覆盖（距离更近）。如果是这样的话，第j个房子的距离被高估了。同时，前j-1个房子的到邮局距离之和也必然被高估，这是因为如果把第j个划归给第k个邮局的话，前k-1个邮局的规划肯定可以更紧密一些。综上所述，对于不合适的j，整个dp[j][k-1] + range[j+1][i]都会偏大。只有遍历到最合适的j，就能得到dp[j][k-1] + range[j+1][i]的最小值，即最小化dp[i][k]。