Leetcode題解 Python：Allocate Mailboxes

給一個陣列 houses ，houses[i]為第 i 個房子的位置，k 為郵筒數，要找出最佳分配下，每房子到最近郵筒的總距離。 

如果郵筒數夠，在每房子前面設一個是最好的，但如果不夠，就會折衷，在房子間找個中間點去設立。

這其實是一個分群的問題。

要設一個郵筒，如果只有二間房子，那最佳位置會在中間。如果三間，那郵筒會在中間的房子前。

換句話說，如果房子有偶數個，在中間那二間之內都可以。如果有奇數個，那只能在中間的房子前。

找到如何決定最佳設置點，接下來就要分 k 組，找到最短的距離總和。

要能決定出一個區間需要有兩個 index， 分別為 l, i。有了 l, i 就能去算距離總和。

用 DFS ，一旦只剩一個郵筒可設，就從只能去算 [l, len(houses)]的距離總和。

如果有二個以上郵筒的可設，就從在 [l,i] 設 或 當前不設 dfs[l, i+1, remain] 的總距離取小者。

或者，以 i 去找 [i,n] 間的選一個位置 j ，將 [i, j]之間的房子配設一個郵筒，然後從中取最小值。

同樣地，若只剩一個郵筒可設，就直接算到 [i, len(houses)] 的距離總和。

這方法好處是少用一個 index，若迴圈定好，也不用做超出邊界的判斷。

Python

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        
        @lru_cache(None)
        def calu_dst(si, ei): 
            avg = houses[(si+ei)//2]
            return sum([abs(num - avg) for num in houses[si:ei]])

        @lru_cache(None)
        def dfs(i, remain):            
            if remain == 1: return calu_dst(i, n) 
            distance = 10000 # 1 <= houses[i] <= 10^4
            for j in range(i+1, n+1-remain+1):  
                distance = min(distance, calu_dst(i, j) + dfs(j, remain-1))             
            return distance
        
        return dfs(0, k)