Allocate Mailboxes LeetCode solution in Java

1
class Solution {
2
  public int minDistance(int[] houses, int k) {
3
    Arrays.sort(houses);
4
    int n = houses.length;
5
    int[] dp = new int[n];
6
    for (int i = 1;
7
        i < n;
8
        i++) { // know optimal dist for i-1, then for i, we add houses[i] - houses[i/2]
9
      dp[i] = dp[i - 1] + houses[i] - houses[i / 2];
10
    }
11
    for (int i = 0; i < k - 1; i++) {
12
      int[] next = new int[n];
13
      Arrays.fill(next, Integer.MAX_VALUE);
14
      for (int j = 0; j < n; j++) {
15
        int sum = 0;
16
        for (int m = j; m >= 0; m--) {
17
          sum +=
18
              houses[(m + j + 1) >> 1]
19
                  - houses[m]; // likewise, adding to the front needs the +1 to account for the
20
          // truncation.
21
          next[j] = Math.min(next[j], (m == 0 ? 0 : dp[m - 1]) + sum);
22
        }
23
      }
24
      dp = next;
25
    }
26
    return dp[n - 1];
27
  }
28
}