Question

1478. 安排邮筒

English Version

题目描述

给你一个房屋数组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 中的整数互不相同。

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i+1$ 栋房子，安排了 $j$ 个邮筒时，每栋房子与离它最近的邮筒之间的距离的最小总和。初始时 $f[i][j]=\infty$，答案即为 $f[n-1][k]$。

我们可以枚举第 $j-1$ 个邮筒“管辖”的最后一栋房子 $p$，即 $0 \leq p \leq i-1$，那么第 $j$ 个邮筒“管辖”的房子就是 $[p+1,..i]$，我们记 $g[i][j]$ 表示给房子 $[i,..j]$ 安排一个邮筒的最小总和，那么有状态转移方程：

$$ f[i][j] = \min_{0 \leq p \leq i-1} {f[p][j-1] + g[p+1][i]} $$

其中 $g[i][j]$ 的计算方法如下：

$$ g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i] $$

时间复杂度 $O(n^2 \times k)$，空间复杂度 $O(n^2)$。其中 $n$ 为房子的数量。

class Solution:
  def minDistance(self, houses: List[int], k: int) -> int:
    houses.sort()
    n = len(houses)
    g = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
      for j in range(i + 1, n):
        g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i]
    f = [[inf] * (k + 1) for _ in range(n)]
    for i in range(n):
      f[i][1] = g[0][i]
      for j in range(2, min(k + 1, i + 2)):
        for p in range(i):
          f[i][j] = min(f[i][j], f[p][j - 1] + g[p + 1][i])
    return f[-1][k]

class Solution {
  public int minDistance(int[] houses, int k) {
    Arrays.sort(houses);
    int n = houses.length;
    int[][] g = new int[n][n];
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i];
      }
    }
    int[][] f = new int[n][k + 1];
    final int inf = 1 << 30;
    for (int[] e : f) {
      Arrays.fill(e, inf);
    }
    for (int i = 0; i < n; ++i) {
      f[i][1] = g[0][i];
      for (int j = 2; j <= k && j <= i + 1; ++j) {
        for (int p = 0; p < i; ++p) {
          f[i][j] = Math.min(f[i][j], f[p][j - 1] + g[p + 1][i]);
        }
      }
    }
    return f[n - 1][k];
  }
}

class Solution {
public:
  int minDistance(vector<int>& houses, int k) {
    int n = houses.size();
    sort(houses.begin(), houses.end());
    int g[n][n];
    memset(g, 0, sizeof(g));
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i];
      }
    }
    int f[n][k + 1];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][1] = g[0][i];
      for (int j = 1; j <= k && j <= i + 1; ++j) {
        for (int p = 0; p < i; ++p) {
          f[i][j] = min(f[i][j], f[p][j - 1] + g[p + 1][i]);
        }
      }
    }
    return f[n - 1][k];
  }
};

func minDistance(houses []int, k int) int {
  sort.Ints(houses)
  n := len(houses)
  g := make([][]int, n)
  f := make([][]int, n)
  const inf = 1 << 30
  for i := range g {
    g[i] = make([]int, n)
    f[i] = make([]int, k+1)
    for j := range f[i] {
      f[i][j] = inf
    }
  }
  for i := n - 2; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      g[i][j] = g[i+1][j-1] + houses[j] - houses[i]
    }
  }
  for i := 0; i < n; i++ {
    f[i][1] = g[0][i]
    for j := 2; j <= k && j <= i+1; j++ {
      for p := 0; p < i; p++ {
        f[i][j] = min(f[i][j], f[p][j-1]+g[p+1][i])
      }
    }
  }
  return f[n-1][k]
}