1478

根据题目首先考虑邮筒的位置，不难想到如果我们可以把邮筒放两个房子的中间，那么两点到这个邮筒的距离不管邮筒如何变动，这个距离都不会变化。更一步的，在多个房子的时候我们取中间的房子放置邮筒，我们两两将最外层房子抛开(因为他们到邮筒的距离都一样)会发现，这个距离依旧是最短的

在预处理所有区间房子的最短距离后，我们采用划分dp即可解出，用dp[i][j] 表达从0到 i 个房子使用j个邮筒的最短距离，我们可以得到dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k+1][i])