题解 | #牛舍安排问题#

牛舍安排问题

https://www.nowcoder.com/practice/b56eb97b8b5941d3a14cd4ce7238f502

大佬的代码。

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]

全部评论

相关推荐

07-23 11:23
门头沟学院 Java
点赞 评论 收藏
分享
06-07 00:00
已编辑
腾讯_后端开发
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务