On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

Have you met this question in a real interview?

Yes

Example

Given array a =[1,2,3,4,5], k = 2.
return3.

1. dp

等同于把问题转化为将 N 所房子分为 k + 1 个路段，求从每一个房子到最近邮局的最短距离和

f[k][i] 表示前k个邮局cover前i个房子的最短距离

f[k][i] = min(f[k - 1][x] + min(A[x - 1]...A[i - 1]) 与第i个邮局的距离和）

initialization

f[0][i] = Integer.MAX_VALUE

f[0][0] = 0

可以看出，需要解决一个问题，就是在只有一个邮局的情况下如何知道在i 到 j的房子到该邮局的最短距离差。

如果这一步可以优化到O(1) 则整个算法可以达到 O(k * n ^2)的时间复杂度

所以可以对这一步进行预处理，把邮局建在左右两端最远的房子的中间一定是最短距离

public class Solution {
    /*
     * @param A: an integer array
     * @param k: An integer
     * @return: an integer
     */
    public int postOffice(int[] A, int k) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        Arrays.sort(A);
        int[][] f = new int[k + 1][A.length + 1];
        int[][] dis = new int[A.length + 1][A.length + 1];

        //1 post office shortest dis sum from house i to j
        for (int i = 1; i <= A.length; i++) {
            for (int j = i + 1; j <= A.length; j++) {
                int mid = i + (j - i) / 2;
                for (int q = i; q <= j; q++) {
                    dis[i][j] += Math.abs(A[q - 1] - A[mid - 1]);
                }
            }
        }

        //initialization f[1][i] = dis[1][i]
        for (int i = 1; i <= A.length; i++) {
            f[1][i] = dis[1][i];
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= A.length; j++) {
                f[i][j] = f[i - 1][j];
                for (int q = 1; q < j; q++) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][q] + dis[q + 1][j]);
                }
            }
        }

        return f[k][A.length];
    }
}