# [题目描述](https://leetcode-cn.com/problems/allocate-mailboxes/)
## 方法1 动态规划
解决这道题我们需要理解以下4点
- 假如只有1个邮筒，N个房子，显然这个邮筒放在最中间(中位数)可以使得所有房子到这个邮筒的距离最小
- 于是我们可以把这道题转换为，怎么用邮筒去把房子分成**若干个区域**，每一个区域内在中位数放邮筒，然后求出最小的距离和 --> 这里就类似**划分数组问题**了，比如[813. 最大平均值和的分组](https://leetcode-cn.com/problems/largest-sum-of-averages/)
- 我们计算`cost[i][j]`表示从`i`到`j`的区域内，放一个邮筒，`[i:j]区域内到这个邮筒的最小距离之和`
- `dp[i][j]`表示从`0~i`区域的房子，放`j`个邮筒(分成`j`块)的最小距离之和；于是有`dp[i][j] = MIN(dp[k-1][j-1] + cost[k][i]),k≤i`
```java
import java.util.Arrays;
public class Solution {
public int superEggDrop(int K, int N) {class Solution {
public int minDistance(int[] houses, int m) {
int n = houses.length;
int[][] cost = new int[n][n];
Arrays.sort(houses);
for(int i = 0;i<n;i++){
for(int j=i;j<n;j++){
int mid = i + (j - i + 1) / 2;
for(int k=i;k<=j;k++){
cost[i][j] += Math.abs(houses[k] - houses[mid]);
}
}
}
int[][] dp = new int[n][m+1];
for(int[] x:dp){
Arrays.fill(x,(int)1e7);
}
for(int i=0;i<n;i++){
for(int j=1;j<m+1;j++){
for(int k = 0; k<=i;k++){
int t = (k>=1)?dp[k-1][j-1]:0;
dp[i][j] = Math.min(dp[i][j],t + cost[k][i]);
}
}
}
return dp[n-1][m];
}
}
```
LeetCode1478. 安排邮筒
