Allocate Mailboxes LeetCode solution in Python

1
class Solution:
2
    def minDistance(self, houses: List[int], k: int) -> int:
3
        houses.sort()
4

5
        @lru_cache(None)
6
        def dp(left, right, k):
7
            if k == 1:  # <-- 1.
8
                mid = houses[(left + right) // 2]
9
                return sum(abs(houses[i] - mid) for i in range(left, right + 1))
10

11
            return min(
12
                dp(left, i, 1) + dp(i + 1, right, k - 1)
13
                for i in range(left, right - k + 2)
14
            )  # <-- 2.
15

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