April 30, 2021: there are residential areas on a straight line, and the post office can only be built on residential areas. Given an ordered positive array arr

2021-04-30： There are settlements on a straight line , Post offices can only be built on residential areas . Given an ordered array of positive numbers arr, Each value represents One dimensional coordinates of the settlement , Give me a positive number num, Indicates the number of post offices . choice num Settlements were established num individual Post Office , Minimize the total distance between all residential areas and the nearest post office , Return the shortest total distance .【 give an example 】arr=1,2,3,4,5,1000,num=2. The first post office was established in 3 Location , The second post office is set up in 1000 Location . that 1 The distance from the location to the post office by 2, 2 The distance from the location to the post office is 1,3 The distance from the location to the post office is 0,4 The distance from the location to the post office is 1, 5 The distance from the location to the post office Leave for 2,1000 The distance from the location to the post office is 0. The total distance under this scheme is 6, The total distance of any other scheme will not Shorter than the total distance of the scheme , So back 6.

Fuda answer 2021-04-30：

Dynamic programming .

The code to use golang To write . The code is as follows ：

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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code