题解 | #牛舍安排问题#

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param houses int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def minTotalDistance(self, houses, k):
        houses.sort()  # Sort the houses' positions
        
        n = len(houses)
        dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            dp[1][i] = self.calculateTotalDistance(houses, 0, i - 1)
        
        for i in range(2, k + 1):
            for j in range(i, n + 1):
                for m in range(i - 1, j):
                    dp[i][j] = min(dp[i][j], dp[i - 1][m] + self.calculateTotalDistance(houses, m, j - 1))
        
        return dp[k][n]

    def calculateTotalDistance(self, houses, start, end):
        median = houses[(start + end) // 2]
        total_distance = 0
        for i in range(start, end + 1):
            total_distance += abs(houses[i] - median)
        return total_distance