邮局选址问题分治法Java代码实现

以下是一个简单的分治法邮局选址问题的Java代码实现：

import java.util.Arrays;

public class PostalOffice {
    
    public static void main(String[] args) {
        int[] houses = {2, 4, 6, 8, 10};
        int numOffices = 3;
        int minDist = getMinDistance(houses, numOffices);
        System.out.println("Minimum distance: " + minDist);
    }
    
    public static int getMinDistance(int[] houses, int numOffices) {
        int n = houses.length;
        int[][] dp = new int[numOffices + 1][n];
        for (int i = 0; i <= numOffices; i++) {
            Arrays.fill(dp[i], -1);
        }
        return minDistance(houses, numOffices, 0, dp);
    }
    
    public static int minDistance(int[] houses, int numOffices, int start, int[][] dp) {
        int n = houses.length;
        if (numOffices == 0) {
            return 0;
        }
        if (dp[numOffices][start] != -1) {
            return dp[numOffices][start];
        }
        int minDist = Integer.MAX_VALUE;
        for (int i = start; i <= n - numOffices; i++) {
            int dist = getDistance(houses, start, i) + minDistance(houses, numOffices - 1, i + 1, dp);
            minDist = Math.min(minDist, dist);
        }
        dp[numOffices][start] = minDist;
        return minDist;
    }
    
    public static int getDistance(int[] houses, int start, int end) {
        int mid = (start + end) / 2;
        int dist = 0;
        for (int i = start; i <= end; i++) {
            dist += Math.abs(houses[i] - houses[mid]);
        }
        return dist;
    }
}

这个实现使用了一个二维数组来存储子问题的解，以避免重复计算。函数`minDistance`采用递归的方式计算最小距离，并返回结果。`getDistance`函数计算了一组房子中心的距离。最后，`getMinDistance`函数初始化了二维数组，并调用`minDistance`函数来计算最小距离。