题解 | #牛舍安排问题#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param houses int整型vector
     * @param k int整型
     * @return int整型
     */
    int minTotalDistance(vector<int>& houses, int k) {
        // write code here
        sort(houses.begin(), houses.end());
        int n = houses.size();

        // 初始化dp数组
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX / 2));
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                for (int p = 0; p < i; p++) {
				  	//在已有分区的情况下，对加入的新牛棚重新按p位置进行分区，重新计算最小值
                    dp[i][j] = min(dp[i][j], dp[p][j - 1] + houses[i - 1] - houses[p]);
                }
            }
        }

        return dp[n][k];
    }
};