安排邮筒

难度: 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 。

示例 3：

输入：houses = [7,4,6,1], k = 1
输出：8

示例 4：

输入：houses = [3,6,14,10], k = 4
输出：0

提示：

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

Submission

运行时间: 73 ms

内存: 16.8 MB

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        #print(houses)
        n = len(houses)

        dp = [[inf] * (k + 1) for _ in range(n)]
        
        one = [[0] * n for _ in range(n)]

        p = [[0] * (k + 1) for _ in range(n)]
        
        dp[0][0] = 0

        pre = [0]
        for i in range(n):
            pre.append(pre[-1] + houses[i])

        for i in range(n):
            for j in range(i + 1, n):
                m = (i + j) // 2
                p1 = (m - i + 1) * houses[m] - (pre[m + 1] - pre[i])
                p2 = pre[j+1] - pre[m + 1] - (j - m) * houses[m]   
                one[i][j] = p1 + p2

        for i in range(n):
            dp[i][1] = one[0][i]
            p[i][1] = 0
        #print(p)
        for kk in range(2, k + 1):
            for i in range(n - 1, -1, -1):
                #if i + 1 <= kk:
                #    dp[i][kk] =  0
                #    p[i][kk] = i // 2
                #    continue
                if i == n - 1:
                    maxNum = n - 1
                else:
                    maxNum = p[i+1][kk]

                minNum = p[i][kk-1]
                #if i == n - 1 and kk == 3:
                #    print("haha: ", minNum, maxNum)
                for j in range(minNum, maxNum + 1):
                    #print(i, j, kk)
                    cost = (dp[j-1][kk - 1] if j > 0 else 0) + one[j][i]
                    #if i == n - 1 and kk == 3:
                    #    print("haha: ", minNum, maxNum)
                    #    print("前面：", dp[j-1][kk-1])
                    #    print("cost: ", cost)
                    
                    if cost <= dp[i][kk]:
                        dp[i][kk] = cost
                        p[i][kk] = j
                    
        #print(p)
        #print(dp)

        return dp[-1][-1]

Explain

这个问题可以通过动态规划来解决。首先，我们对房屋位置进行排序，使得问题变得更容易处理。定义dp[i][j]表示前i+1个房屋安排j个邮筒的最小距离总和。数组one[i][j]用于存储从i到j的房子只用一个邮筒时的最小总距离，其中邮筒放在中位数位置能够达到最小距离。我们首先计算所有可能的one[i][j]值。然后，使用动态规划填充dp数组。对于每个dp[i][j]，我们尝试所有可能的前一个状态dp[k][j-1]（其中k < i），并加上从k+1到i的房屋使用一个邮筒的距离，即one[k+1][i]。通过这种方式，我们可以构建出所有房屋和邮筒配置的最小距离总和。

时间复杂度: O(n^2 * k)

空间复杂度: O(n^2 + n * k)

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)

        # 初始化dp数组和one数组
        dp = [[float('inf')] * (k + 1) for _ in range(n)]
        one = [[0] * n for _ in range(n)]

        # 计算房屋位置的前缀和
        pre = [0]
        for i in range(n):
            pre.append(pre[-1] + houses[i])

        # 计算所有one[i][j]值
        for i in range(n):
            for j in range(i + 1, n):
                m = (i + j) // 2
                p1 = (m - i + 1) * houses[m] - (pre[m + 1] - pre[i])
                p2 = pre[j+1] - pre[m + 1] - (j - m) * houses[m]
                one[i][j] = p1 + p2

        # 使用动态规划求解最小距离总和
        for i in range(n):
            dp[i][1] = one[0][i]
        for kk in range(2, k + 1):
            for i in range(n - 1, -1, -1):
                if i == n - 1:
                    maxNum = n - 1
                else:
                    maxNum = p[i+1][kk]
                minNum = p[i][kk-1]
                for j in range(minNum, maxNum + 1):
                    cost = (dp[j-1][kk - 1] if j > 0 else 0) + one[j][i]
                    if cost <= dp[i][kk]:
                        dp[i][kk] = cost
                        p[i][kk] = j
        return dp[-1][-1]

Explore

对房屋位置进行排序的目的是为了简化计算和优化算法的实现。在已排序的房屋位置列表中，任意子区间[i, j]（i <= j）的房屋都是连续的，并且位置是递增的。这样便于计算这些房屋到一个邮筒的最短距离，因为邮筒放在中位数位置时能达到最小总距离，而中位数很容易从排序后的列表中得到。此外，排序后的列表也便于使用动态规划方法计算不同房屋分组的最小距离，因为每次分割都是基于连续的子序列。

当邮筒放在一组房屋的中位数位置时，可以最小化到所有房屋的距离总和。这是因为中位数的特性是它将数据集分成两个数量大致相等的部分，从而使得左边和右边房屋到邮筒的距离总和达到最小。具体来说，将邮筒置于中位数位置，对于中位数左侧的每一步向左移动，左侧房屋到邮筒的距离会增加，但右侧的会减少；由于右侧房屋数量不少于左侧，总距离因此减少。同理，向右移动邮筒也遵循类似的逻辑。因此，中位数是最优位置。

在计算one数组时，p1和p2的计算关键在于确定中位数房屋左侧和右侧房屋到邮筒的距离总和。具体来说，p1计算的是从i到m（中位数）房屋的距离总和，p2计算的是从m+1到j房屋的距离总和。公式中，(m - i + 1) * houses[m] 表示中位数到所有左侧房屋（包括中位数本身）的距离乘以房屋数量，pre数组用于快速计算区间和，即pre[m+1] - pre[i]是i到m的房屋位置和。同理，p2中的pre[j+1] - pre[m+1]表示m+1到j的房屋位置和，(j - m) * houses[m]则是这些房屋到中位数的距离乘以房屋数量。这样，p1 + p2就给出了所有房屋到中位数邮筒的总距离。