Hard

题目描述

给你一个房屋数组 houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮箱。

请你返回每栋房子与离它最近的邮箱之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

示例 1：

输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮箱分别安装在位置 3， 9 和 20 处。
每个房子到最近邮箱的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例 2：

输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮箱分别安装在位置 3 和 14 处。
每个房子到最近邮箱的距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

提示：

  • 1 <= k <= houses.length <= 100
  • 1 <= houses[i] <= 10^4
  • houses 中的整数互不相同

思路提示：

  • 如果 k=1，最小距离通过将邮箱分配在房屋数组的中位数处获得
  • 推广这个思路，使用动态规划分配 k 个邮箱

解题思路

这是一个典型的动态规划问题，核心思路如下：

关键观察：

  1. 对于任意连续区间的房屋，最优的邮箱位置是中位数位置，这样能使总距离最小
  2. 我们需要将房屋分成k个连续的区间，每个区间放置一个邮箱

解法思路：

  1. 首先对房屋位置进行排序，确保我们处理的是有序序列
  2. 预处理：计算任意区间[i,j]内放置一个邮箱的最小代价cost[i][j]
  3. 动态规划：定义dp[i][j]表示前i栋房子使用j个邮箱的最小总距离
  4. 状态转移：dp[i][j] = min(dp[t][j-1] + cost[t+1][i]) 对所有有效的t

预处理cost数组：

  • 对于区间[i,j]，最优邮箱位置是中位数houses[(i+j)/2]
  • cost[i][j]就是该区间所有房屋到中位数的距离之和

时间复杂度： 预处理O(n³)，DP O(n²k) 空间复杂度： O(n²)用于cost数组，O(nk)用于DP数组

代码实现

class Solution {
public:
    int minDistance(vector<int>& houses, int k) {
        int n = houses.size();
        sort(houses.begin(), houses.end());
        
        // 预处理：计算区间[i,j]放置一个邮箱的最小代价
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2];
                for (int t = i; t <= j; t++) {
                    cost[i][j] += abs(houses[t] - median);
                }
            }
        }
        
        // dp[i][j]表示前i个房子用j个邮箱的最小代价
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    if (dp[t][j-1] != INT_MAX) {
                        dp[i][j] = min(dp[i][j], dp[t][j-1] + cost[t][i-1]);
                    }
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        n = len(houses)
        houses.sort()
        
        # 预处理：计算区间[i,j]放置一个邮箱的最小代价
        cost = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                median = houses[(i + j) // 2]
                for t in range(i, j + 1):
                    cost[i][j] += abs(houses[t] - median)
        
        # dp[i][j]表示前i个房子用j个邮箱的最小代价
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                for t in range(j - 1, i):
                    if dp[t][j-1] != float('inf'):
                        dp[i][j] = min(dp[i][j], dp[t][j-1] + cost[t][i-1])
        
        return dp[n][k]

public class Solution {
    public int MinDistance(int[] houses, int k) {
        int n = houses.Length;
        Array.Sort(houses);
        
        // 预处理：计算区间[i,j]放置一个邮箱的最小代价
        int[,] cost = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2];
                for (int t = i; t <= j; t++) {
                    cost[i, j] += Math.Abs(houses[t] - median);
                }
            }
        }
        
        // dp[i,j]表示前i个房子用j个邮箱的最小代价
        int[,] dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.Min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    if (dp[t, j-1] != int.MaxValue) {
                        dp[i, j] = Math.Min(dp[i, j], dp[t, j-1] + cost[t, i-1]);
                    }
                }
            }
        }
        
        return dp[n, k];
    }
}

var minDistance = function(houses, k) {
    const n = houses.length;
    houses.sort((a, b) => a - b);
    
    // 预处理：计算区间[i,j]放置一个邮箱的最小代价
    const cost = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const median = houses[Math.floor((i + j) / 2)];
            for (let t = i; t <= j; t++) {
                cost[i][j] += Math.abs(houses[t] - median);
            }
        }
    }
    
    // dp[i][j]表示前i个房子用j个邮箱的最小代价
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(Infinity));
    dp[0][0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= Math.min(i, k); j++) {
            for (let t = j - 1; t < i; t++) {
                if (dp[t][j-1] !== Infinity) {
                    dp[i][j] = Math.min(dp[i][j], dp[t][j-1] + cost[t][i-1]);
                }
            }
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
动态规划O(n³ + n²k)O(n² + nk)
说明预处理cost数组需要O(n³)，DP过程需要O(n²k)cost数组占用O(n²)，dp数组占用O(nk)