> 我在网上看到的dp是假设k, j之间新设一个邮局是在中点的位置， 但是这个位置会不会发生k之前的村庄离新邮局更近， 而不是离前一个邮局更近？ 这样f[i-1][k] + cost[k+1][j]就不是最短的距离了？

这种DP是对的，但是正确性不是显然的。重新定义一下符号。f[i][k]表示前i个村庄建k个邮局。状态转移是f[i][k] = min_m { f[m][k-1] + c[m+1][i]  }

对于某个m，的确可能出现最后一个邮局和前面的村庄更近的情况。这样f[m][k-1] + c[m+1][i]要大于对应邮局分布Tm下的实际距离，即：对任意m, f[m][k-1] + c[m+1][i]>=d(Tm)。对于最优分布T*, 设前k-1个邮局覆盖了n个村, 可以证明f[n][k-1]+c[n+1][i]=d(T*)，即等号可取到，所以DP结果是对的。

但网上几乎所有的解题报告在这里一点说明都没有，估计是认为所有情况下等号都成立，这是误打误撞。