LeetCode 1478. 安排邮筒
题目描述
原题：1478. 安排邮筒。
给定一条直线上互不相同的房屋位置houses和邮筒数量k，放置k个邮筒，使所有房屋到最近邮筒的距离之和最小。返回最小距离和。约束1≤k≤n≤100，房屋位置在1…10000。
示例 1：
输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：可在位置 1、8、20 放邮筒，五栋房屋的最近距离分别为 0、3、0、2、0，总和为 5。
提示：
- 1≤k≤n≤100；房屋位置互不相同，均在 1…10000。距离按直线上两点坐标差的绝对值计算。
题意分析
在一条直线上放置
k个邮筒，让每栋房屋到最近邮筒的距离之和尽可能小，返回这个最小总距离。房屋位置互不相同，邮筒可以服务多栋房屋，不要求各邮筒服务数量相等，也不要求邮筒等间距。目标是所有房屋距离的总和，不是最远房屋的距离。题目保证
k <= n；当邮筒数等于房屋数时，每栋房屋放一个邮筒，总距离自然为零。
解法：区间中位数费用与分组 DP
核心思路
[!blue]
先按位置排序。若把邮筒也从左到右排列，两个相邻邮筒之间的房屋会按距离分界选择最近者，因此每个邮筒负责的房屋可以取为一段连续区间。遇到等距时统一选择一侧即可，不需要考虑互相交叉的分配。问题由此变成：把有序房屋分成
k个连续组，每组使用一个邮筒，最小化各组费用之和。对一组房屋，一个邮筒放在中位数位置最优。可以从两端向中间配对理解：一对位置为
a <= b的房屋，只要邮筒位于它们之间，总距离就是b - a；落在外面反而更大。各对区间的共同部分就是中位数位置，或偶数栋时两个中间位置之间，所以在那里能同时使所有配对费用最小。定义
cost[l][r]为房屋闭区间[l, r]由一个邮筒服务的最小费用。去掉最外层一对后，内部的中位数仍在外层两端之间，因此有cost[l][r] = houses[r] - houses[l] + cost[l + 1][r - 1]。单栋费用为零，两栋费用就是坐标差；预处理时让左端从大到小，保证内部区间已经计算。再定义
dp[g][i]为恰好用g个邮筒服务前i栋房屋的最小费用。枚举最后一组从下标j开始，则前j栋由g - 1个邮筒服务，最后一组费用为cost[j][i - 1]，转移取dp[g - 1][j] + cost[j][i - 1]的最小值。每组都非空，所以
i >= g，最后起点满足g - 1 <= j < i。任意合法分组都有唯一的最后起点，枚举它不会漏掉最优方案；之前各组与最后一组费用独立相加，使用前缀最优值也不会影响最后一组的安排。只有
dp[0][0] = 0是初始可行状态，其余先设为足够大的值，避免把“没有邮筒却服务了房屋”误当成零费用。最终读取dp[k][n]。当前代码直接排序输入数组，会改变房屋原先的排列顺序。
解题步骤
- 邮筒足够给每栋房屋单独使用时返回零，否则先排序房屋位置。
- 预处理所有连续区间的单邮筒费用，单点为零，更长区间由两端距离加内部费用得到。
- 初始化分组 DP 为不可达，仅将
dp[0][0]设为零。- 按邮筒数和前缀房屋数递增，枚举最后一组的起点，取前缀费用与末组费用之和的最小值。
- 返回
dp[k][n]。
代码实现
class Solution {
public int minDistance(int[] houses, int k) {
int n = houses.length;
if (k >= n) {
return 0;
}
Arrays.sort(houses);
int[][] cost = new int[n][n];
for (int l = n - 1; l >= 0; l--) {
for (int r = l + 1; r < n; r++) {
cost[l][r] = houses[r] - houses[l] + (r - l > 1 ? cost[l + 1][r - 1] : 0);
}
}
int[][] dp = new int[k + 1][n + 1];
for (int[] row : dp) {
Arrays.fill(row, 1_000_000_000);
}
dp[0][0] = 0;
for (int g = 1; g <= k; g++) {
for (int i = g; i <= n; i++) {
for (int j = g - 1; j < i; j++) {
dp[g][i] = Math.min(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
}
}
}
return dp[k][n];
}
}
import "sort"
func minDistance(houses []int, k int) int {
n := len(houses)
if k >= n {
return 0
}
sort.Ints(houses)
cost := make([][]int, n)
for i := range cost {
cost[i] = make([]int, n)
}
for l := n - 1; l >= 0; l-- {
for r := l + 1; r < n; r++ {
cost[l][r] = houses[r] - houses[l]
if r-l > 1 {
cost[l][r] += cost[l+1][r-1]
}
}
}
dp := make([][]int, k+1)
for i := range dp {
dp[i] = make([]int, n+1)
for j := range dp[i] {
dp[i][j] = 1_000_000_000
}
}
dp[0][0] = 0
for g := 1; g <= k; g++ {
for i := g; i <= n; i++ {
for j := g - 1; j < i; j++ {
dp[g][i] = min(dp[g][i], dp[g-1][j]+cost[j][i-1])
}
}
}
return dp[k][n]
}
复杂度分析
- 时间复杂度：$O(kn^2+n\log n)$。排序为 $O(n\log n)$，区间费用为 $O(n^2)$，分组状态枚举最后起点合计为 $O(kn^2)$。
- 空间复杂度：$O(n^2+kn)$，分别保存单组区间费用表和分组 DP 表。
关键点总结
[!green]
- 排序把最近邮筒分配化为连续分组，中位数解决单组内部最优位置。
- 两端配对解释了单邮筒费用递推，不必对每个区间再逐栋计算距离。
- 分组 DP 枚举最后一组，状态中的
i是房屋数量，费用表下标则是实际房屋下标。
易错点总结
[!yellow]
- 邮筒按等间距放置，忽略房屋分布，并不能保证总距离最小。
- 用平均值替代中位数，会混淆绝对距离和与平方距离和的最优位置。
- DP 全部初始化为零，会把本来不可达的前缀当成可以免费覆盖。
- 最后一组范围应为
[j, i - 1]，并要求j < i，不能算成空组或多包含一栋。- 忽略单栋一组，会漏掉允许每个邮筒只服务一栋房屋的合法方案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 813. 最大平均值和的分组 | 中等 | 同样枚举最后一组起点，原题单组收益为平均值，本题单组代价为到中位数的距离和。 |
| 410. 分割数组的最大值 | 困难 | 都是有序连续分组，本题最小化各组费用之和，原题最小化最大组和，不能直接复用同一判定。 |