1478. Allocate Mailboxes

Problem Link

Description

---

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.

Solution

---

Python3

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        N = len(houses)
        houses.sort()
        costs = [[0] * N for _ in range(N)] # total travel distance from houses[i : j] to the median mailbox
 
        for i in range(N):
            for j in range(N):
                median = houses[(i + j) // 2]
                for m in range(i, j + 1):
                    costs[i][j] += abs(median - houses[m])
        
        @cache
        def go(i, k):
            if i == N: return 0
 
            if k == 0 or i == N: return inf
                
            res = inf
            for j in range(i, N):
                cost = costs[i][j]
                res = min(res, go(j + 1, k - 1) + cost)
 
            return res
        
        return go(0, k)