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):

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