python3 解法, 执行用时: 360 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-21 17:58:39

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        cost = [[0] * n for _ in range(n)]
        presum = [0] + list(accumulate(houses))
        for i in range(n):
            for j in range(i, n):
                l = j - i + 1
                point = i + l//2
                cost[i][j] = presum[j + 1] - presum[point] * 2 + presum[i] - (houses[point] if l % 2 else 0)
        
        dp = list(cost[0])
        for _ in range(k - 1):
            for i in range(n-1, -1, -1):
                for j in range(i):
                    dp[i] = min(dp[i], dp[j] + cost[j+1][i])
        return dp[-1]

golang 解法, 执行用时: 0 ms, 内存消耗: 3.1 MB, 提交时间: 2023-06-21 17:58:21

func minDistance(houses []int, k int) int {
    sort.Ints(houses)
    n := len(houses)
    presum := make([]int, n + 1)
    for i := 0; i < n; i++ {
        presum[i + 1] = presum[i] + houses[i];
    }
    cost := make([][]int, n)
    for i := 0; i < n; i++ {
        cost[i] = make([]int, n)
        for j := i; j < n; j++ {
            l := j - i + 1
            point := i + l / 2
            cost[i][j] = presum[j + 1] - presum[point] * 2 + presum[i]
            if l & 1 > 0 {
                cost[i][j] -= houses[point]
            }
        }
    }
    dp := make([]int, n)
    copy(dp, cost[0])
    for m := 0; m < k - 1; m++ {
        for r := n - 1; r >= 0; r-- {
            for l := 0; l < r; l++ {
                if v:= dp[l] + cost[l + 1][r]; v < dp[r]{
                    dp[r] = v
                }
            }
        }
    }
    return dp[n - 1]
}

java 解法, 执行用时: 7 ms, 内存消耗: 39.7 MB, 提交时间: 2023-06-21 17:57:20

class Solution {
    public int minDistance(int[] houses, int k) {
        int n = houses.length;
        Arrays.sort(houses);

        int[][] medsum = new int[n][n];
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                medsum[i][j] = medsum[i + 1][j - 1] + houses[j] - houses[i];
            }
        }

        int[][] f = new int[n][k + 1];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], Integer.MAX_VALUE / 2);
        }
        for (int i = 0; i < n; ++i) {
            f[i][1] = medsum[0][i];
            for (int j = 2; j <= k && j <= i + 1; ++j) {
                for (int i0 = 0; i0 < i; ++i0) {
                    f[i][j] = Math.min(f[i][j], f[i0][j - 1] + medsum[i0 + 1][i]);
                }
            }
        }

        return f[n - 1][k];
    }
}

python3 解法, 执行用时: 304 ms, 内存消耗: 16.7 MB, 提交时间: 2023-06-21 17:56:59

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        n = len(houses)
        houses.sort()

        medsum = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                medsum[i][j] = medsum[i + 1][j - 1] + houses[j] - houses[i]
        
        BIG = 10**9
        f = [[BIG] * (k + 1) for _ in range(n)]
        for i in range(n):
            f[i][1] = medsum[0][i]
            for j in range(2, min(k, i + 1) + 1):
                for i0 in range(i):
                    if f[i0][j - 1] != BIG:
                        f[i][j] = min(f[i][j], f[i0][j - 1] + medsum[i0 + 1][i])
        
        return f[n - 1][k]

cpp 解法, 执行用时: 36 ms, 内存消耗: 9.2 MB, 提交时间: 2023-06-21 17:56:19

/**
 * 动态规划
 * dp[i][j] 前i个房子放置j个邮箱的最小距离
 * 
 **/
class Solution {
public:
    int minDistance(vector<int>& houses, int k) {
        int n=houses.size();
        //排序
        sort(houses.begin(),houses.end());

        //计算最小花费
        vector<vector<int>> d(n,vector<int>(n,1e8));
        //初始化
        for(int i=0;i<n;i++) d[i][i]=0;
        for(int i=0;i<n-1;i++) d[i][i+1]=houses[i+1]-houses[i];
        //状态转移
        for(int j=2;j<n;j++){
            for(int i=j-2;i>=0;i--){
                d[i][j]=d[i+1][j-1]+houses[j]-houses[i];
            }
        }
        
        //dp
        vector<vector<int>> dp(n,vector<int>(k+1,1e8));
        //初始化
        for(int i=0;i<n;i++) dp[i][1]=d[0][i];
        for(int j=2;j<=k;j++){
            for(int i=j-1;i<n;i++){
                //穷举分割状态转移
                for(int xt=0;xt<i;xt++){
                    dp[i][j]=min(dp[i][j],dp[xt][j-1]+d[xt+1][i]);
                }
            }
        }
        return dp[n-1][k];
    }
};

python3 解法, 执行用时: 292 ms, 内存消耗: 17.5 MB, 提交时间: 2023-06-21 17:53:21

# 记忆化 + dfs
class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        pre = [0]
        l = len(houses)
        for i in range(l):
            pre.append(pre[-1] + houses[i])
        
        #i, k分别是房屋下标和剩余邮筒数量
        @lru_cache(None)
        def dfs(i: int, k: int):
            #如果邮筒数量大于等于房子数量，那么距离和一定为0
            if l - i <= k:
                return 0
            #如果邮筒数量为1
            elif k == 1:
                #中位数
                j = (l + i) // 2
                #中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小
                return houses[j] * (j - i) - (pre[j] - pre[i]) + pre[l] - pre[j] - houses[j] * (l - j)
            #当前邮筒只覆盖一个房子
            res = dfs(i + 1, k - 1)
            #覆盖多个房子
            for n in range(i + 1, l):
                #中位数
                j = (n + 1 + i) // 2
                #中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小 + 继续深搜的结果
                res = min(res, houses[j] * (j - i) - (pre[j] - pre[i]) + pre[n + 1] - pre[j] - houses[j] * (n + 1 - j) + dfs(n + 1, k - 1))
            return res
        return dfs(0, k)