#
# 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
#
# 
# @param houses int整型一維數(shù)組 
# @param k int整型 
# @return int整型
#
class Solution:
    def minTotalDistance(self , houses: List[int], k: int) -> int:
        houses.sort()
        dp = [[float('inf')]*(k+1) for _ in range(len(houses)+1)]
        for j in range(k+1):
            dp[0][j] = 0
        for i in range(1,len(houses)+1):
            for j in range(1,k+1):
                for l in range(j-1,i):
                    dp[i][j] = min(dp[i][j], dp[l][j-1]+self.best(houses,l,i))
        return dp[-1][-1]
    def best(self, houses, left, right):
        res = 0
        mid = (left+right) //2
        for x in houses[left:right]:
            res += abs(x-houses[mid])
        return res