1478. Allocate Mailboxes


题目

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点赞!


发表回复

您的电子邮箱地址不会被公开。