Allocate Mailboxes

class Solution {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        if(k >= houses.length) return 0;
        int[][] dp = new int[houses.length][k+1];
        
        for(int i = 0; i<dp.length; i++){
            Arrays.fill(dp[i], 100000000);
        }
        
        for(int i = houses.length-1; i>=0; i--){
            for(int j = k; j>=1; j--){
                if(j >= (houses.length-i)){
                    dp[i][j] = 0;
                }
                else{
                    int sum = 0;
                    int minDist = Integer.MAX_VALUE;
                    boolean add = false;
                    for(int l = i, z = i; l<=(houses.length-j); l++){
                        //System.out.println("hi");
                        sum += (houses[l] - houses[z]);
                        //System.out.println((l+1<houses.length ? dp[l+1][j-1] : 0));
                        minDist = Math.min(minDist, sum + (l+1<houses.length ? dp[l+1][j-1] : 0));
                        if(add) z++;
                        add = !add;
                    }
                    //System.out.println(minDist);
                    dp[i][j] = minDist;
                }
            }
        }
        //System.out.println(Arrays.deepToString(dp));
        return dp[0][k];
    }
}