2021-04-30：一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示 居民点的

2021-04-30：一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组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。

福大大 答案2021-04-30：

动态规划。

代码用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
    }
}

执行结果如下：

左神java代码