Allocate Mailboxes

Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Example 3:

Input: houses = [7,4,6,1], k = 1
Output: 8

Example 4:

Input: houses = [3,6,14,10], k = 4
Output: 0

Constraints:

n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
Array houses contain unique integers.

Solution:

Idea
The idea is we try to allocate each mailbox to k group of the consecutive houses houses[i:j]. We found a solution if we can distribute total k mailboxes to n houses devided into k groups [0..i], [i+1..j], ..., [l..n-1].
After all, we choose the minimum cost among our solutions.

(Attached image from Leetcode for easy to understand the idea)

costs[i][j] is the cost to put a mailbox among houses[i:j], the best way is put the mail box at median position among houses[i:j]

class Solution {
    final int max = 1000000;
    
    public int minDistance(int[] houses, int k) {
        int n = houses.length;
        Arrays.sort(houses);
        Integer[][] memo = new Integer[n][n + 1];
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; i ++) {
            for (int j = i; j < n; j ++) {
                for (int m = i; m <= j; m ++) {
                    cost[i][j] += Math.abs(houses[(i + j) / 2] - houses[m]);
                }
            }
        }
        return helper(houses, cost, memo, 0, k, n);
    }
    
    private int helper(int[] houses, int[][] cost, Integer[][] memo, int i, int k, int n) {
        if (k == 0 && i == n) return 0;
        if (k == 0 || i == n) return max;
        if (memo[i][k] != null) return memo[i][k];
        int c = max;
        for (int j = i; j < n; j ++) {
            c = Math.min(c, helper(houses, cost, memo, j + 1, k - 1, n) + cost[i][j]);
        }
        return memo[i][k] = c;
    }
}