C++刷LeetCode（1478. 安排邮筒）【动态规划】

糖逗

题目描述：

1. 给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
   
2. 
   
3. 请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
   
4. 
   
5. 答案保证在 32 位有符号整数范围以内。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：houses = [1,4,8,10,20], k = 3
    
14. 输出：5
    
15. 解释：将邮筒分别安放在位置 3， 9 和 20 处。
    
16. 每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
    
17. 示例 2：
    
18. 
    
19. 
    
20. 
    
21. 输入：houses = [2,3,5,12,18], k = 2
    
22. 输出：9
    
23. 解释：将邮筒分别安放在位置 3 和 14 处。
    
24. 每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
    
25. 示例 3：
    
26. 
    
27. 输入：houses = [7,4,6,1], k = 1
    
28. 输出：8
    
29. 示例 4：
    
30. 
    
31. 输入：houses = [3,6,14,10], k = 4
    
32. 输出：0
    
33.  
    
34. 
    
35. 提示：
    
36. 
    
37. n == houses.length
    
38. 1 <= n&#160;<= 100
    
39. 1 <= houses[i] <= 10^4
    
40. 1 <= k <= n
    
41. 数组&#160;houses&#160;中的整数互不相同。
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/allocate-mailboxes
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minDistance(vector<int>& houses, int k) {
   
4.         sort(houses.begin(),houses.end());//注意这一步
   
5.         int len = houses.size();
   
6.         vector<vector<int> >cost(len, vector<int>(len, 0));
   
7.         for(int i = 0; i < len; i++){
   
8.             for(int j = i + 1; j < len; j++){
   
9.                 int mid = (i + j) / 2;//注意这里的写法
   
10.                 for(int k = i; k <= j; k++){
    
11.                     cost[i][j] += abs(houses[k]-houses[mid]);
    
12.                 }
    
13.             }
    
14.         }
    
15.         vector<vector<int> > dp(len, vector<int>(k + 1, INT_MAX));
    
16.         for(int i = 0; i < len; i++){
    
17.             dp[i][1] = cost[0][i];
    
18.         }
    
19.         for(int i = 0; i < len; i++){
    
20.             for(int j = 2; j <= k; j++){
    
21.                 for(int k = j - 1; k <= i; k++){
    
22.                     dp[i][j] = min(dp[i][j], dp[k-1][j-1] + cost[k][i]);
    
23.                 }
    
24.             }
    
25.         }
    
26.         return dp[len-1][k];
    
27.     }
    
28. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -tong-by-qi-yi-lin/

糖逗

这道题需要之后再看一遍