题解 | #牛舍安排问题#

#include <algorithm>
#define INF 0x3f3f3f3f

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param houses int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int cost_fun(vector<int>& houses, int i, int j) {
        int mid = (i + j) >> 1;
        int cost = 0;
        for (int h = i; h <= j; ++h) 
        {
            cost += abs(houses[h] - houses[mid]);
        }
        return cost;
    }

    int dp_fun(vector<int>& dp, vector<vector<int>>& cost, int i) {
        int minv = cost[0][i];
        for (int m = 1; m <= i; ++m) {
            minv = min(minv, dp[m - 1] + cost[m][i]);  // [0---m-1]分配j-1  [m---i]分配1
        }
        return minv;
    }

    int minTotalDistance(vector<int>& houses, int k) {
        // 计算cost数组
        vector<vector<int>> cost(houses.size(), vector<int>(houses.size(), 0));
        for (int i = 0; i < houses.size(); i++)
        {
            for (int j = i; j < houses.size(); j++)
            {
                cost[i][j] = cost_fun(houses, i, j);
            }

        }
        // dp数组 init 仅与 j-1
        vector<int> dp(houses.size(), INF);  // [i,j=0]
        for (int j = 1; j < k + 1; ++j) {
            for (int i = houses.size()-1; i >= 0; --i) {
                // 求得最小值
                dp[i] = dp_fun(dp, cost, i);
            }
            dp[0] = 0;
        }
        return dp[houses.size()-1];
    }
};