题解 | #牛舍安排问题#

int calMinDistance(int* house, int housesLen, int index) {
    int totalDistance = 0;
    int median = (housesLen + index) / 2;

    for (int i = index; i < housesLen; ++i) {
        int distance = house[i] > house[median] ? house[i] - house[median] :
                       house[median] - house[i];
        totalDistance += distance;
    }

    return totalDistance;
}


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param houses int整型一维数组
 * @param housesLen int houses数组长度
 * @param k int整型
 * @return int整型
 */
int minTotalDistance(int* houses, int housesLen, int k) {

    // 定义动态规划数组，dp[i][j]表示前i栋牛舍分配j个喂食区的情况下，
    // 前i栋牛舍离最近的喂食区之前的距离总和最小值
    int** dp = (int**)malloc(sizeof(int*) * (housesLen + 1));
    for (int i = 0; i < housesLen + 1; ++i) {
        dp[i] = (int*)malloc(sizeof(int) * (k + 1));
    }

    // 处理边界值，若牛舍数量为0，则无论分配多少个喂食区，距离之和都是0
    for (int j = 0; j < k + 1; ++j) {
        dp[0][j] = 0;
    }

    // 定义初始值，只要牛舍数量不为0，那么默认距离之和为最大值
    for (int i = 1; i < housesLen + 1; ++i) {
        for (int j = 0; j < k + 1; ++j) {
            dp[i][j] = 2147483627;
        }
    }

    // 遍历处理，i代表前i栋牛舍
    for (int i = 1; i < housesLen + 1; ++i) {
        // j代表分配j个喂食区
        for (int j = 1; j < k + 1; ++j) {
            // m表示把前m个牛舍分配j-1个喂食区，
            // 剩下的i-m个牛舍分配1个喂食区
            for (int m = 0; m < i; ++m) {
                if (dp[m][j - 1] == 2147483627) continue;
                if (dp[i][j] > dp[m][j - 1] + calMinDistance(houses, i, m)) {
                    dp[i][j] = dp[m][j - 1] + calMinDistance(houses, i, m);
                }
            }
        }
    }

    int result = dp[housesLen][k];

    for (int i = 0; i < housesLen + 1; ++i) {
        free(dp[i]);
    }
    free(dp);

    return result;
}