题目

Given the array houses where houses[i] is the location of the ith house along a street and an integer k, allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Constraints:

• 1 <= k <= houses.length <= 100
• 1 <= houses[i] <= 104
• All the integers of houses are unique.

思路

题目大意是给定houses数组，放置k个mailbox，使得所有house到各自最近的mailbox的距离之和最小。

数据量比较大（100），有可复用的状态（前面的邮箱放好了以后一定程度上不影响后面的house和mailbox），直觉上看是个dp问题。

来分析下，一般来说（剔除掉k>n这种边边角角的case），n个house，分配k个mailbox，相当于把n个house按照“离哪个mailbox最近”分成k个部分，如下图。

按照这个思路，已经前面已经划分好的house的最小距离和就和后面没有关系了。

状态定义&转移方程

尝试定义下状态。

dp[i][j][k]，表示houses[i: j +1]区间里，设立k个mailbox的最小距离和。

那么在每一次自顶向下尝试求dp[i][j][k]的时候，我们可以穷举一个子区间houses[i: w + 1]，尝试在houses[i: w + 1]中设立一个mailbox，这样总的最小距离为dp[i][w][1] + dp[w + 1][j][k – 1]。

穷举w对结果取最小值，就可以得到dp[i][j][k]。

于是我们有下面的状态转移方程

dp[i][j][k] = dp[i][w][1] + dp[w + 1][j][k – 1]

dp[i][j][1] = min_dist(i, j) = min(sum(abs(arr[k] – x))), i <= k <= j

其中，min_dist(i, j)表示在house[i: j + 1]中设立1个mailbox，使得house[i: j + 1]到这个mailbox的距离和最小，即min(sum(abs(arr[k] – x))), i <= k <= j

看起来很顺利对不。

不过等等，这里状态表示真的是不受其他状态干扰的吗？

刨根问题一下，很多人都会被这个问题绕进去——case如下图。

可以看到，这种情况下，h[k]离我们前面区间求出来的mailbox1更近，这种方法求出来的min_dist[i][j]是比最优值更大的。

这是不是说明，我们定义的状态方程是有问题的呢？

其实我们只要抓住重点就好。

所有的组合都会被遍历是吗？——是的。（虽然有可能dp[i][j][1]，即min_dist(i, j)可能会比最小值偏大）

那如果恰好遍历到了最优解，min_dist(i, j)能保证恰好等于最小值吗？——显然可以

——那不就结了

——如此看来，我们对dp[i][j][k]的定义不太恰当，dp[i][j][1]不是houses[i: j +1]种设立1个mailbox的距离之和最小值，而是”houses[i: j +1]种设立1个mailbox的距离之和最小值的上界“，且在最优划分下dp[i][j][1]等于houses[i:j + 1]下设立1个mailbox的距离和的最小值。

状态转移方程优化

再来看看状态转移方程，其实按照我们的递推方法，三维转移方程有点冗余了，完全可以改成二维。

dp[i][k]为前i个houses设立k个mailbox的距离和最小值

dp[i][k] = min(dp[j][k – 1] + min_dist(j + 1, k)), 其中1<=j<=k

子问题：对于houses[i:j + 1]，求min_dist(i, j)

对houses[i: j + 1]，在x处设立一个mailbox，使得sum(abs(x – house[w]))最小（i<=w<=k)。

这里不展开了，直接上结论：x应该取houses[i: j +1]的中位数，证明可以见链接。

【但是我用的是穷举法，幸好时间复杂度差不多。】

代码

ok有了前面的分析，代码就很好写了。

代码是按优化前的状态和转移方程来写的，实际时间复杂度是一样的。

class Solution(object):
    def minDistance(self, houses, k):
        """
        :type houses: List[int]
        :type k: int
        :rtype: int
        """
        houses = sorted(houses)
        lsum = [houses[0]]
        for i in range(1, len(houses)):
            lsum.append(lsum[-1] + houses[i])
            
            
        # [i, j] k == 1, special case / min distance for [i,j].
        def helper(i, j):
            ret = None
            for w in range(i, j + 1):
                abs1 = (w - i + 1) * houses[w] - (lsum[w] - (lsum[i - 1] if i > 0 else 0))
                abs2 = (lsum[j] - lsum[w]) - (j - w) * houses[w]
                ret = abs1 + abs2 if ret is None else min(abs1 + abs2, ret)
            return ret
            
            
        m = {}
        def dp(i, j, k):
            if (i, j, k) in m:
                return m[(i, j, k)]
            if k == 1:
                m[(i, j, k)] = helper(i, j)
                return m[(i, j, k)]
            elif k >= j - i + 1:
                return 0
            ret = None
            for w in range(i, j):
                cur_ans = dp(i, w, 1) + dp(w + 1, j, k - 1)
                ret = cur_ans if ret is None else min(cur_ans, ret)
            m[(i, j, k)] = ret
            return ret
        
        return dp(0, len(houses) - 1, k)

提交上去，ac，收工！

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/07/02/leetcode-1478-allocate-mailboxes/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！