题解 | #牛舍安排问题#

大佬的代码。

dp解决，因为的n的数值小，所以时间复杂度为O(n³)也可以。

class Solution:
    def distance(self, houses, i, j):
      dis = 0
      m = (i+j) // 2
      for k in range(i,j+1):
        dis += abs(houses[k-1] - houses[m-1])
      return dis

    def minTotalDistance(self , houses: List[int], k: int) -> int:
        houses.sort()
        #定义dp数组,dp[i][j]表示i个数前分成j组的最小距离
        dp = [[float('inf') for _ in range(k+1)] for _ in range(len(houses)+1)]

        for h in range(1, len(houses) + 1):
            dp[h][1] = self.distance(houses, 1, h)

        for i in range(1, len(houses)+1):
            for j in range(2, k+1):
                for t in range(j-1, i+1):
                    dis = self.distance(houses, t, i)
                    dp[i][j] = min(dp[i][j], dp[t-1][j-1] + dis)
                    
        return dp[len(houses)][k]