# 1478. Allocate Mailboxes

## 题目

Given the array `houses` where `houses[i]` is the location of the `ith` house along a street and an integer `k`, allocate `k` mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

```Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5
```

Example 2:

```Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.
```

Constraints:

• `1 <= k <= houses.length <= 100`
• `1 <= houses[i] <= 104`
• All the integers of `houses` are unique.

## 思路

### 状态定义&转移方程

dp[i][j][k]，表示houses[i: j +1]区间里，设立k个mailbox的最小距离和。

dp[i][j][k] = dp[i][w][1] + dp[w + 1][j][k – 1]

dp[i][j][1] = min_dist(i, j) = min(sum(abs(arr[k] – x))), i <= k <= j

——那不就结了

——如此看来，我们对dp[i][j][k]的定义不太恰当，dp[i][j][1]不是houses[i: j +1]种设立1个mailbox的距离之和最小值，而是”houses[i: j +1]种设立1个mailbox的距离之和最小值的上界“，且在最优划分下dp[i][j][1]等于houses[i:j + 1]下设立1个mailbox的距离和的最小值。

### 状态转移方程优化

dp[i][k]为前i个houses设立k个mailbox的距离和最小值

dp[i][k] = min(dp[j][k – 1] + min_dist(j + 1, k)), 其中1<=j<=k

### 子问题：对于houses[i:j + 1]，求min_dist(i, j)

【但是我用的是穷举法，幸好时间复杂度差不多。】

## 代码

ok有了前面的分析，代码就很好写了。

``````class Solution(object):
def minDistance(self, houses, k):
"""
:type houses: List[int]
:type k: int
:rtype: int
"""
houses = sorted(houses)
lsum = [houses[0]]
for i in range(1, len(houses)):
lsum.append(lsum[-1] + houses[i])

# [i, j] k == 1, special case / min distance for [i,j].
def helper(i, j):
ret = None
for w in range(i, j + 1):
abs1 = (w - i + 1) * houses[w] - (lsum[w] - (lsum[i - 1] if i > 0 else 0))
abs2 = (lsum[j] - lsum[w]) - (j - w) * houses[w]
ret = abs1 + abs2 if ret is None else min(abs1 + abs2, ret)
return ret

m = {}
def dp(i, j, k):
if (i, j, k) in m:
return m[(i, j, k)]
if k == 1:
m[(i, j, k)] = helper(i, j)
return m[(i, j, k)]
elif k >= j - i + 1:
return 0
ret = None
for w in range(i, j):
cur_ans = dp(i, w, 1) + dp(w + 1, j, k - 1)
ret = cur_ans if ret is None else min(cur_ans, ret)
m[(i, j, k)] = ret
return ret

return dp(0, len(houses) - 1, k)``````

——此处是内容的分割线——