安排邮筒

/*
 * 问题描述：给定一组房屋位置和k个邮筒，找出将邮筒放置在街道上的位置，使得每栋房子到最近邮筒的距离之和最小。
 * 
 * 思路：
 * 1. 由于Java Stream API不能直接用于复杂的动态规划问题，所以我们使用stream对数组进行排序和计算距离。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class MinDistanceToMailboxStream {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n = houses.length;
        int[][] dp = new int[n + 1][k + 1];
        int[][] cost = new int[n + 1][n + 1];

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2];
                final int left = i;
                final int right = j;
                cost[i + 1][j + 1] = IntStream.rangeClosed(i, j)
                        .map(idx -> Math.abs(houses[idx] - median))
                        .sum();
            }
        }

        IntStream.range(1, n + 1).forEach(i -> Arrays.fill(dp[i], Integer.MAX_VALUE / 2));
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                for (int m = 0; m < i; m++) {
                    dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + cost[m + 1][i]);
                }
            }
        }

        return dp[n][k];
    }
}