Post Office

給出m個村莊及其距離，給出n個郵局，要求怎麼建n個郵局使代價最小.

On one line there are n houses. Give you an array of integer means 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.

Example

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

Challenge

Could you solve this problem in O(n^2) time ?

解题思路：DP

dis[i][j]表示在第i個村庄和第j個村庄中間造一間郵局的情況下，所有村莊到郵局的距離和 dp[i][l] 表示在前i個村莊建l間郵局的最小距離和

計算dp[i][l] 的方式：

從第 1 座村莊到第 i 座村莊找出一個切點 j 使得滿足以下條件
    前 j 個村莊蓋 l - 1 間郵局，加上在第 j + 1 個村莊到第 i 個村莊的中間蓋一間郵局的矩離和最小。
    dp[i][l] = dp[j][l - 1] + dis[j + 1][i]

private int[][] init(int[] A){
        int n = A.length;
        int[][] dis = new int[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                int mid = (i+j)/2;
                for(int k = i; k <= j; k++){
                    dis[i][j] += Math.abs(A[k-1] - A[mid-1]);
                }
            }
        }
        return dis;
    }

    public int postOffice(int[] A, int k) {
        int n = A.length;
        Arrays.sort(A);
        int[][] dp = new int[n+1][n+1];
        int[][] dis = init(A);

        if(n == 0 || k >= A.length) return 0;

        //前i間房只能蓋一間郵局的話，就不斷的把郵局蓋在前i間房的中間
        for(int i = 0; i <= n; i++){
            dp[i][1] = dis[1][i];
        }

        for(int l = 2; l <= k; l++){//post数量
            for(int i=l; i <= n; i++){
                dp[i][l] = Integer.MAX_VALUE;

                for(int j = 0; j < i; j++){
                    if(dp[i][l] == Integer.MAX_VALUE || dp[i][l] > (dp[j][l-1] + dis[j+1][i])){
                        dp[i][l] = dp[j][l-1] + dis[j+1][i];
                    }
                }
            }
        }
        return dp[n][k];
    }