C++刷LeetCode（1478. 安排邮筒）【动态规划】
题目描述：给你一个房屋数组houses 和一个整数 k ，其中 houses 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
答案保证在 32 位有符号整数范围以内。
示例 1：
输入：houses = , k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：
输入：houses = , k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：
输入：houses = , k = 1
输出：8
示例 4：
输入：houses = , k = 4
输出：0
提示：
n == houses.length
1 <= n <= 100
1 <= houses <= 10^4
1 <= k <= n
数组 houses 中的整数互不相同。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/allocate-mailboxes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minDistance(vector<int>& houses, int k) {
sort(houses.begin(),houses.end());//注意这一步
int len = houses.size();
vector<vector<int> >cost(len, vector<int>(len, 0));
for(int i = 0; i < len; i++){
for(int j = i + 1; j < len; j++){
int mid = (i + j) / 2;//注意这里的写法
for(int k = i; k <= j; k++){
cost += abs(houses-houses);
}
}
}
vector<vector<int> > dp(len, vector<int>(k + 1, INT_MAX));
for(int i = 0; i < len; i++){
dp = cost;
}
for(int i = 0; i < len; i++){
for(int j = 2; j <= k; j++){
for(int k = j - 1; k <= i; k++){
dp = min(dp, dp + cost);
}
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/allocate-mailboxes/solution/an-pai-you-tong-by-qi-yi-lin/ 这道题需要之后再看一遍
页:
[1]