Given the array houses
and an integer k
. where houses[i]
is the location of the ith house along a street, your task is to allocate k
mailboxes in the street.
Return the minimum total distance between each house and its nearest mailbox.
The answer is guaranteed to fit in a 32-bit signed 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.
Example 3:
Input: houses = [7,4,6,1], k = 1 Output: 8
Example 4:
Input: houses = [3,6,14,10], k = 4 Output: 0
Constraints:
n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
- Array
houses
contain unique integers.
Solution: DP
First, we need to sort the houses by their location.
This is a partitioning problem, e.g. optimal solution to partition first N houses into K groups. (allocating K mailboxes for the first N houses).
The key of this problem is to solve a base case, optimally allocating one mailbox for houses[i~j], The intuition is to put the mailbox in the middle location, this only works if there are only tow houses, or all the houses are evenly distributed. The correct location is the “median position” of a set of houses. For example, if the sorted locations are [1,2,3,100], the average will be 26 which costs 146 while the median is 2, and the cost becomes 100.
dp[i][k] := min cost to allocate k mailboxes houses[0~i].
base cases:
- dp[i][1] = cost(0, i), min cost to allocate one mailbox.
- dp[i][k] = 0 if k > i, more mailboxes than houses. // this is actually a pruning.
transition:
dp[i][k] = min(dp[p][k-1] + cost(p + 1, i)) 0 <= p < i,
allocate k-1 mailboxes for houses[0~p], and allocate one for houses[p+1~i]
ans:
dp[n-1][k]
Time complexity: O(n^3)
Space complexity: O(n^2) -> O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Author: Huahua class Solution { public: int minDistance(vector<int>& houses, int k) { constexpr int kInf = 1e9; const int n = houses.size(); sort(begin(houses), end(houses)); vector<vector<int>> dp(n + 1, vector<int>(n + 1, kInf)); vector<vector<int>> costs(n + 1, vector<int>(n + 1, kInf)); // min cost to allocate one mailbox for houses[i~j]. auto cost = [&](int i, int j) { int& ans = costs[i][j]; if (ans != kInf) return ans; const int m = i + (j - i) / 2; int box = 0; if ((j - i + 1) & 1) // odd number of houses. box = houses[m]; else // even number of houses. box = (houses[m] + houses[m + 1]) / 2; ans = 0; for (int h = i; h <= j; ++h) ans += abs(houses[h] - box); return ans; }; // min cost to allocate k mailboxes for houses[0~i]. function<int(int, int)> solve = [&](int i, int k) { if (k > i) return 0; // more mailboxs than houses. if (k == 1) return cost(0, i); int& ans = dp[i][k]; if (ans != kInf) return ans; for (int p = 0; p < i; ++p) ans = min(ans, solve(p, k - 1) + cost(p + 1, i)); return ans; }; return solve(n - 1, k); } }; |
O(1) time to compute cost. O(n) Time and space for pre-processing.
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua vector<int> sums(n + 1); for (int i = 1; i <= n; ++i) sums[i] = sums[i - 1] + houses[i - 1]; // min cost to allocate one mailbox for houses[i~j]. auto cost = [&](int i, int j) { const int m1 = (i + j) / 2; const int m2 = (i + j + 1) / 2; const int center = (houses[m1] + houses[m2]) / 2; return (m1 - i + 1) * center - (sums[m1 + 1] - sums[i]) + (sums[j + 1] - sums[m2]) - (j - m2 + 1) * center; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment