题解 | #牛舍安排问题#动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param houses int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def minTotalDistance(self , houses: List[int], k: int) -> int:
        houses.sort()  # 排序牛舍位置
        n = len(houses)
        
        # 创建动态规划数组
        dp = [[0] * (k + 1) for _ in range(n)]
        
        # 计算任意两个牛舍之间的距离
        def calculate_distance(i, j):
            return abs(houses[i] - houses[j])

        # 填充动态规划数组
        for i in range(n):
            for j in range(k + 1):
                if j == 0:
                    dp[i][j] = 0
                elif i == 0:
                    dp[i][j] = 0
                elif j == 1:
                    dp[i][j] = calculate_distance(0, i)
                else:
                    min_dist = float('inf')
                    for x in range(i):
                        min_dist = min(min_dist, dp[x][j - 1] + calculate_distance(x + 1, i))
                    dp[i][j] = min_dist

        # 返回最小距离总和
        return dp[n - 1][k]

1. 定义动态规划数组： 创建一个二维动态规划数组 dp，其中 dp[i][j] 表示将前 i 个牛舍分成 j 个喂食区时的最小距离总和。

2. 初始化动态规划数组： 初始化动态规划数组 dp。对于 dp[i][1]，它表示只有一个喂食区，那么最小距离总和就是最后一个牛舍与第一个牛舍的距离。对于 dp[i][j]（j > 1），我们可以将它分解成两部分：

• 一个喂食区位于 houses[i] 处，此时 dp[i][j] = dp[i-1][j-1]。
• 一个喂食区位于 houses[i] 之前的某个位置 houses[x] 处，此时 dp[i][j] = dp[x][j-1] + (houses[i] - houses[x])，其中 x 的范围是 [0, i-1]。

3. 填充动态规划数组： 使用两个嵌套循环来填充动态规划数组 dp，外循环遍历牛舍的位置 i，内循环遍历喂食区的数量 j。在填充过程中，根据上述初始化步骤中的公式来更新 dp[i][j]。

4. 寻找最小距离总和： 在填充完整个动态规划数组后，最小距离总和将位于 dp[n-1][k]，其中 n 是牛舍位置的数量，k 是喂食区的数量。

5. 返回结果： 返回 dp[n-1][k] 作为最小距离总和的答案。