前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
给定一个正整数数组和一个num，其中arr[i]代表第i个居民所在的一维空间的位置，如arr=[1,2,3,4,5,1000],代表arr[4] 在位置4，arr[5]在位置1000，那么arr[4]和arr[5]之间的距离为1000-5 = 995
num为邮局的数量，现在邮局需要放置在若干居民的位置上，求如何放置邮局位置才能使的所有居民到邮局的距离之和最短？
解决方案
暴力递归
略
动态规划：
动态规划之前，我们先计算出来一个二维数组w，其中w[i][j]代表arr[i…j]由一个邮局来解决时，最终的最短距离，如何求w？
w[i][j] = w[i-1][j] + arr[j] - arr[(i+j)/2]
要素一：dp[i][j]代表 i个画匠完成 arr[0…j]个居民位置所产生的最短距离
要素二：dp[i][j] 的计算方式：
· 游标k从j到0，依次代表 arr[k…j]由第一个邮局负责，剩下的arr[0…k]由剩下的i-1个邮局完成，求所有可能性中的最小值即可
四边形不等式优化动态规划
在原动态规划基础上，限制第三层循环尝试的x的范围：
·如果dp[i-1][j]获取到最少的距离，此时k值记录为l，后面计算dp[i][j]时，k值将不再小于l
·如果dp[i][j+1]获取到最少的距离，此时k值记录为r，后面计算dp[i][j]时，k值将不再大于r
根据以上两点可以确定尝试x的范围在[l…r]，具体四边形不等式的证明非常多，这里不再证明
代码编写
java语言版本
基本动态规划：
/**
* 二轮测试：动态规划解法
* @return
*/
public static int solution1Cp1(int[] arr, int num) {
if (arr == null || num == 0) {
return -1;
}
// wArr[i][j] 表示 arr[i...j]中只放一个邮局时需要的最短距离数
int[][] wArr = getWArr(arr);
// dp[i][j]代表i个邮局解决 arr[0..j]的居民问题
int[][] dp = new int[num + 1][arr.length];
// 初始化dp
dp[1][0] = 0;
for (int j = 1; j < dp[0].length; j++) {
dp[1][j] = wArr[0][j];
}
// 动态规划主体
for (int i = 2; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (j <= i) {
// 每一个居民都能分到邮局，直接没有距离
dp[i][j] = 0;
continue;
}
int min = Integer.MAX_VALUE;
// 第一个邮局负责arr[k...j]，剩下的负责arr[0..k-1]
for (int k = j; k >= 1; k--) {
// 第一个邮局解决的最短距离
int first = wArr[k][j];
int second = dp[i-1][k-1];
min = Math.min(min, first+second);
}
dp[i][j] = min;
}
}
return dp[num][arr.length-1];
}
/**
* wArr[i][j] 表示 arr[i...j]中只放一个邮局时需要的最短距离数
* @param arr
* @return
*/
private static int[][] getWArr(int[] arr) {
int[][] wArr = new int[arr.length][arr.length];
// 只需要填充上半部分
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
// 这里需要解释一下，中点因为两边的元素数目相同（偶数特殊，但也相同），滑动时保持两边数相同时能够保证总合不变
wArr[i][j] = wArr[i][j-1] + arr[j] - arr[(i+j)/2];
}
}
return wArr;
}
四边形不等式优化动态规划
/**
* 二轮测试：四边形不等式
* @return
*/
public static int solution2Cp2(int[] arr, int num) {
if (arr == null || num == 0) {
return -1;
}
// wArr[i][j] 表示 arr[i...j]中只放一个邮局时需要的最短距离数
int[][] wArr = getWArr(arr);
// dp[i][j]代表i个邮局解决 arr[0..j]的居民问题的最短距离
int[][] dp = new int[num + 1][arr.length];
// map[i][j]代表i个邮局解决 arr[0..j]的居民问题最优解时的k值
int[][] map = new int[num + 1][arr.length];
// 初始化dp
dp[1][0] = 0;
for (int j = 1; j < dp[0].length; j++) {
dp[1][j] = wArr[0][j];
}
// 动态规划主体
for (int i = 2; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (j <= i) {
// 每一个居民都能分到邮局，直接没有距离
dp[i][j] = 0;
continue;
}
int min = Integer.MAX_VALUE;
// 左边至少给一个居民让给剩下的邮局，因为邮局至少有两个
int l = map[i-1][j] == 0 ? 1 : map[i-1][j];
int r = j == dp[0].length-1 ? dp[0].length-1 : map[i][j+1];
// 第一个邮局负责arr[k...j]，剩下的负责arr[0..k-1]
for (int k = r; k >= l; k--) {
// 第一个邮局解决的最短距离
int first = wArr[k][j];
int second = dp[i-1][k-1];
if (first + second < min) {
min = first+second;
map[i][j] = k;
}
}
dp[i][j] = min;
}
}
return dp[num][arr.length-1];
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
有兴趣可以对比一下画匠问题，发现我的解法和画匠问题一模一样的思路，我自己都觉得这篇文章有点水了哈哈
这道题跟画匠问题有一个差别就是w矩阵的计算，这个计算方式是怎么来的？
比如arr = [1,2,3,4,5,8,10]，毫无疑问4的位置可以让所有的位置之和最终最短，
我们可以发现如果从4移动到5，整体的距离之和会发生什么变化？
1原本距离4为3，现在距离多了一个1
2多了一个1
3多了一个1
4原本是9，现在也多了一个1
5原本是1，现在少了一个1
8原来是4，现在是3，少了一个1
10原来是6，现在是5，少了一个1
因此整体变化量是多了一个1，因为现在k的位置已经不在中点了
那么现在如果多一个位置12，整体就是[1,2,3,4,5,8,10,12]，我们会发现如果原本的4到5多出来的那个1其实会被12的出现”中和掉“，好好体会
那么现在的整体[1,2,3,4,5,8,10,12]的最短距离应该由“[1,2,3,4,5,8,10]的最短距离” 和 “12这个多出来的数字-中点” 这两个数字组成，还是很巧妙的。