Lintcode 435. Post Office Problem

435. Post Office Problem

中文English

There are n houses on a line. Given an array A and A[i] represents the position of i-th house. Now you need to pick k position to build k post offices.

What is the minimum sum distance from these n houses to the nearest post office?

Example

Example 1:

Input: A = [1, 2, 3, 4, 5], k = 2
Output: 3
Explanation: Build post offices on position 2 and 4.

Example 2:

Input: A = [1, 2], k = 1
Output: 1
Explanation: Build post office on position 1 or 2.

Challenge

O($n^2$) time

Notice

All positions are integers.

Analysis:
The problem is a sequence DP problem. 
We define dp[n + 1][k + 1] where dp[i][j] means for the first i houses build j post offices, what's the min sum of distance? 

dp[i][j] = min {dp[m][j - 1] + dist[m + 1][i]}, m is [1, i - 1]
where dist[m + 1][i] means the min sum of distance building one post office from m+1th house to ith house. 

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

public class Solution {     /**      * @param A: an integer array      * @param k: An integer      * @return: an integer      */     public int postOffice(int[] A, int k) {         if (A == null || A.length == 0 || k <= 0) {             return 0;         }                   Arrays.sort(A);                   int n = A.length;                   // dp[i][j] means for the first i houses build j post offices, what's the         // min sum of distance         int[][] dp = new int[n + 1][k + 1];                   // dist[i][j] means from ith house to jth house, if build one postOffice,         // what's the min sum of distance         int[][] dist = new int[n + 1][n + 1]; //                   // init dist         for (int i = 1; i <= n; i++) {             for (int j = i + 1; j <= n; j++) {                 int mid = (i + j) / 2;                                   for (int m = i; m <= j; m++) {                     dist[i][j] += Math.abs(A[m - 1] - A[mid - 1]);                 }             }         }                   // init dp         for (int i = 1; i <= n; i++) {             dp[i][1] = dist[1][i];         }                   for (int nk = 2; nk <= k; nk++) {             for (int i = nk; i <= n; i++) {                 dp[i][nk] = Integer.MAX_VALUE;                 for (int j = 1; j < i; j++) {                     if (dp[j][nk - 1] != Integer.MAX_VALUE && dp[j][nk - 1] + dist[j + 1][i] < dp[i][nk])                     dp[i][nk] = dp[j][nk - 1] + dist[j + 1][i];                 }             }         }                   return dp[n][k];     } }