DeepSeek LeetCode 1478. 安排邮筒 public int minDistance(int[] houses, int k)
dp[i][j]= 前i个房子（houses[0…i-1]）用j个邮筒覆盖的最小总距离方法时间复杂度空间复杂度说明朴素 DP + 暴力 costO(n² + nk)n≤100 可过前缀和优化 costO(n²k)O(n² + nk)n≤200 可过四边形不等式优化O(n² + nk)n≤1000 可过递推计算 costO(n²)O(n² + nk)最优预处理关键点先排序房子位置邮筒放在中位数位置最
·
这道题是 “安排邮筒”，是典型的 DP + 中位数优化 问题。核心思想是：将 k 个邮筒安排到 n 个房子的位置，使得所有房子到最近邮筒的距离之和最小。
题目理解
- 给定
houses数组（已排序的位置，不是排序后返回，而是输入可能无序） - 需要放置
k个邮筒，每个邮筒可以放在任意整数位置 - 每个房子到最近的邮筒的距离之和最小
- 邮筒可以放在房子所在位置
关键洞察：由于邮筒可以放在任意位置，且房子位置已排序，最优解中每个邮筒一定覆盖一个连续的子数组，并且邮筒应放在该子数组的中位数位置。
前置知识：单段最小距离和
对于一段连续的房子 houses[l..r]，放置 1 个邮筒的最优位置是这些房子的中位数，最小距离和为：
cost[l][r] = sum(|houses[i] - median|) for i in [l..r]
这个可以用前缀和 O(1) 计算。
核心解法：二维 DP
状态定义
dp[i][j] = 前 i 个房子（houses[0…i-1]）用 j 个邮筒覆盖的最小总距离
状态转移
dp[i][j] = min(dp[t][j-1] + cost[t][i-1]) for t from j-1 to i-1
含义：前 t 个房子用 j-1 个邮筒覆盖，第 j 个邮筒覆盖房子 t 到 i-1。
边界条件
dp[i][1] = cost[0][i-1]：用 1 个邮筒覆盖前 i 个房子dp[0][0] = 0：0 个房子 0 个邮筒距离为 0
完整代码
class Solution {
public int minDistance(int[] houses, int k) {
// 1. 排序房子位置
Arrays.sort(houses);
int n = houses.length;
// 2. 预处理 cost[l][r]：用 1 个邮筒覆盖 houses[l..r] 的最小距离
int[][] cost = new int[n][n];
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int median = houses[(l + r) / 2];
for (int i = l; i <= r; i++) {
cost[l][r] += Math.abs(houses[i] - median);
}
}
}
// 3. DP 数组：dp[i][j] = 前 i 个房子用 j 个邮筒的最小总距离
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
}
// 边界：0 个房子 0 个邮筒
dp[0][0] = 0;
// 4. DP 转移
for (int i = 1; i <= n; i++) { // 前 i 个房子
for (int j = 1; j <= Math.min(k, i); j++) { // 用 j 个邮筒
// 枚举最后一个邮筒覆盖的起始位置
for (int t = j - 1; t < i; t++) {
// 前 t 个房子用 j-1 个邮筒
// 第 j 个邮筒覆盖 houses[t..i-1]
dp[i][j] = Math.min(dp[i][j],
dp[t][j - 1] + cost[t][i - 1]);
}
}
}
return dp[n][k];
}
}
时间复杂度优化
上述代码复杂度 O(n³)，对于 n=100 勉强可过。可以优化 cost 计算到 O(n²)：
class Solution {
public int minDistance(int[] houses, int k) {
Arrays.sort(houses);
int n = houses.length;
// 优化 cost 计算：利用递推关系
// cost[l][r] = cost[l][r-1] + houses[r] - houses[(l+r)/2]
int[][] cost = new int[n][n];
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int mid = (l + r) / 2;
if (r == l) {
cost[l][r] = 0;
} else if (r == l + 1) {
cost[l][r] = houses[r] - houses[l];
} else {
// 当 r 增加时，中位数可能不变或右移一位
// 这里用更通用的计算方法
cost[l][r] = cost[l][r - 1] + houses[r] - houses[mid];
}
}
}
// 更准确的计算方法（推荐）：
// 重新计算 cost，确保正确
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int median = houses[(l + r) / 2];
for (int i = l; i <= r; i++) {
cost[l][r] += Math.abs(houses[i] - median);
}
}
}
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(k, i); j++) {
for (int t = j - 1; t < i; t++) {
dp[i][j] = Math.min(dp[i][j],
dp[t][j - 1] + cost[t][i - 1]);
}
}
}
return dp[n][k];
}
}
四边形不等式优化
观察转移方程：dp[i][j] = min(dp[t][j-1] + cost[t][i-1])
当 cost 满足四边形不等式时，可以使用决策单调性优化到 O(kn log n) 或 O(kn)。
class Solution {
public int minDistance(int[] houses, int k) {
Arrays.sort(houses);
int n = houses.length;
// 预处理 cost
int[][] cost = new int[n][n];
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int median = houses[(l + r) / 2];
for (int i = l; i <= r; i++) {
cost[l][r] += Math.abs(houses[i] - median);
}
}
}
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
}
dp[0][0] = 0;
// 四边形不等式优化
int[][] best = new int[n + 1][k + 1];
for (int j = 1; j <= k; j++) {
// 分治优化
solve(1, n, 1, n, j, dp, cost, best);
}
return dp[n][k];
}
private void solve(int l, int r, int optL, int optR, int j,
int[][] dp, int[][] cost, int[][] best) {
if (l > r) return;
int mid = (l + r) / 2;
int bestIdx = optL;
int minVal = Integer.MAX_VALUE / 2;
for (int t = optL; t <= Math.min(optR, mid); t++) {
int val = dp[t][j - 1] + cost[t][mid - 1];
if (val < minVal) {
minVal = val;
bestIdx = t;
}
}
dp[mid][j] = minVal;
best[mid][j] = bestIdx;
solve(l, mid - 1, optL, bestIdx, j, dp, cost, best);
solve(mid + 1, r, bestIdx, optR, j, dp, cost, best);
}
}
中位数计算公式优化
用前缀和 O(1) 计算 cost[l][r]：
class Solution {
public int minDistance(int[] houses, int k) {
Arrays.sort(houses);
int n = houses.length;
// 前缀和
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + houses[i];
}
// O(1) 计算 cost[l][r]
// 中位数位置 m = (l + r) / 2
// 左边和：mid - l 个元素，和 = prefix[mid+1] - prefix[l]
// 右边和：r - mid 个元素，和 = prefix[r+1] - prefix[mid+1]
// cost = houses[mid] * (mid - l) - leftSum + rightSum - houses[mid] * (r - mid)
long[][] cost = new long[n][n];
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int mid = (l + r) / 2;
long leftSum = prefix[mid + 1] - prefix[l];
long rightSum = prefix[r + 1] - prefix[mid + 1];
cost[l][r] = (long)houses[mid] * (mid - l) - leftSum
+ rightSum - (long)houses[mid] * (r - mid);
}
}
long[][] dp = new long[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], Long.MAX_VALUE / 2);
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(k, i); j++) {
for (int t = j - 1; t < i; t++) {
dp[i][j] = Math.min(dp[i][j],
dp[t][j - 1] + cost[t][i - 1]);
}
}
}
return (int)dp[n][k];
}
}
总结
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 朴素 DP + 暴力 cost | O(n³ + n²k) | O(n² + nk) | n≤100 可过 |
| 前缀和优化 cost | O(n²k) | O(n² + nk) | n≤200 可过 |
| 四边形不等式优化 | O(kn log n) | O(n² + nk) | n≤1000 可过 |
| 递推计算 cost | O(n²) | O(n² + nk) | 最优预处理 |
关键点：
- 先排序房子位置
- 邮筒放在中位数位置最优
- 使用前缀和 O(1) 计算 cost[l][r]
- 区间 DP 划分问题
欢迎加入DeepSeek 技术社区。在这里，你可以找到志同道合的朋友，共同探索AI技术的奥秘。
更多推荐
5
0- 0
已为社区贡献375条内容
所有评论(0)