一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示 居民点的一维坐标，再给定一个正数 num，表示邮局数量。选择num个居民点建立num个 邮局，使所有的居民点到最近邮局的总距离最短，返回最短的总距离。【举例】arr=[1,2,3,4,5,1000]，num=2。第一个邮局建立在 3 位置，第二个邮局建立在 1000 位置。那么 1 位置到邮局的距离 为 2， 2 位置到邮局距离为 1，3 位置到邮局的距离为 0，4 位置到邮局的距离为 1， 5 位置到邮局的距 离为 2，1000 位置到邮局的距离为 0。这种方案下的总距离为 6， 其他任何方案的总距离都不会 比该方案的总距离更短，所以返回6。
动态规划。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{1, 2, 3, 4, 5, 1000}
num := 2
ret := min1(arr, num)
fmt.Println(ret)
//ret = min2(arr, num)
//fmt.Println(ret)
}
func min1(arr []int, num int) int {
if num < 1 || len(arr) < num {
return 0
}
N := len(arr)
w := make([][]int, N+1)
for i := 0; i < N+1; i++ {
w[i] = make([]int, N+1)
}
for L := 0; L < N; L++ {
for R := L + 1; R < N; R++ {
w[L][R] = w[L][R-1] + arr[R] - arr[(L+R)>>1]
}
}
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, num+1)
}
for i := 0; i < N; i++ {
dp[i][1] = w[0][i]
}
for i := 1; i < N; i++ {
for j := 2; j <= getMin(i, num); j++ {
ans := math.MaxInt32
for k := 0; k <= i; k++ {
ans = getMin(ans, dp[k][j-1]+w[k+1][i])
}
dp[i][j] = ans
}
}
return dp[N-1][num]
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
//func min2(arr []int, num int) int {
// if num < 1 || len(arr) < num {
// return 0
// }
// N := len(arr)
// w := make([][]int, N+1)
// for i := 0; i < N+1; i++ {
// w[i] = make([]int, N+1)
// }
// for L := 0; L < N; L++ {
// for R := L + 1; R < N; R++ {
// w[L][R] = w[L][R-1] + arr[R] - arr[(L+R)>>1]
// }
// }
//
// dp := make([][]int, N)
// for i := 0; i < N; i++ {
// dp[i] = make([]int, num+1)
// }
//
// best := make([][]int, N)
// for i := 0; i < N; i++ {
// best[i] = make([]int, num+1)
// }
// for i := 0; i < N; i++ {
// dp[i][1] = w[0][i]
// best[i][1] = -1
// }
// for j := 2; j <= num; j++ {
// for i := N - 1; i >= j; i-- {
// down := best[i][j-1]
// up := twoSelectOne(i == N-1, N-1, best[i+1][j])
// ans := math.MaxInt32
// bestChoose := -1
// for leftEnd := down; leftEnd <= up; leftEnd++ {
// leftCost := twoSelectOne(leftEnd == -1, 0, dp[leftEnd][j-1])
// rightCost := twoSelectOne(leftEnd == i, 0, w[leftEnd+1][i])
// cur := leftCost + rightCost
// if cur <= ans {
// ans = cur
// bestChoose = leftEnd
// }
// }
// dp[i][j] = ans
// best[i][j] = bestChoose
// }
// }
// return dp[N-1][num]
//}
func twoSelectOne(isSelectFirst bool, a int, b int) int {
if isSelectFirst {
return a
} else {
return b
}
}执行结果如下：
