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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
int dp[101][101][101];
int helper(vector<int>& houses, int left, int right, int k) {
if(k <= 0 or right >= houses.size()) {
return right == houses.size() and k == 0 ? 0 : INT_MAX;
}
if(dp[left][right][k] != -1) return dp[left][right][k];
int& res = dp[left][right][k] = helper(houses,right + 1, right + 1, k - 1);
if(res != INT_MAX) {
for(int i = left; i <= right; i++) {
res += abs(houses[(left + right) / 2] - houses[i]);
}
}
return res = min(res, helper(houses,left, right + 1, k));
}
public:
int minDistance(vector<int>& houses, int k) {
memset(dp,-1,sizeof(dp));
sort(houses.begin(), houses.end());
return helper(houses,0,0,k);
}
};
|
