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

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

The test cases are generated so that the answer fits in a 32-bit integer.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= k &lt;= houses.length &lt;= 100
	1 &lt;= houses[i] &lt;= 104
	All the integers of houses are unique.


class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()

        @lru_cache(None)
        def dp(left, right, k):
            if k == 1:                                          # <-- 1.
                mid = houses[(left+right) // 2]
                return sum(abs(houses[i] - mid) for i in range(left, right + 1))

            return min(dp(left, i, 1) + dp(i+1, right, k - 1) 
                       for i in range(left, right - k + 2))     # <-- 2.

        return dp(0, len(houses)-1, k)
class Solution {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n = houses.length;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++){ // know optimal dist for i-1, then for i, we add houses[i] - houses[i/2]
            dp[i]=dp[i-1]+houses[i]-houses[i/2];
        }
        for (int i = 0; i < k-1; i++){
            int[] next = new int[n];
            Arrays.fill(next, Integer.MAX_VALUE);
            for (int j = 0; j < n; j++){
                int sum = 0;
                for (int m = j; m >= 0; m--){
                    sum += houses[(m+j+1)>>1]-houses[m]; // likewise, adding to the front needs the +1 to account for the truncation.
                    next[j] = Math.min(next[j], (m==0?0:dp[m-1])+sum);
                }
            }
            dp=next;
        }
        return dp[n-1];
    }
}
class Solution {
public:
    int dp[101][101] ;
    int solve(vector<int>&houses , int pos , int k){
        if(k < 0) return 1e9 ;
        if(pos >= houses.size()) return k ? 1e9 : 0 ; 
        if(dp[pos][k] != -1) return dp[pos][k] ;
        
        //at current position pos, spread the group from (pos upto j) and allot this whole group 1 mailbox.
        //start new neigbour at j + 1
        
        int ans = INT_MAX ;
        for(int j = pos ; j < houses.size() ; ++j ){
            int middle = (pos + j) / 2 , cost = 0 ;
            //cost calculation
            for(int i = pos ; i <= j ; ++i ) cost += abs(houses[middle] - houses[i]);
            
            ans = min(ans,cost + solve(houses,j + 1, k - 1)) ;
        }
        return dp[pos][k] = ans ;
    }
    int minDistance(vector<int>& houses, int k) {
        sort(begin(houses),end(houses)) ;
        memset(dp,-1,sizeof(dp)) ;
        
        return solve(houses,0,k);
    }
};
/**
 * @param {number[]} houses
 * @param {number} k
 * @return {number}
 */
var minDistance = function(houses, k) {
    var distance=[],median,dist,cache={};
    houses.sort(function(a,b){return a-b});
    //distance[i][j] is the minimun distacne if we cover houses from ith index to jth index with 1 mailbox. This mailbox will be at the median index of sub array from ith index to jth index.
    for(let i=0;i<houses.length;i++){
        for(let j=i;j<houses.length;j++){
            median = Math.floor((i+j)/2);
            dist=0;
            for(let k=i;k<=j;k++){
                dist+=Math.abs(houses[median]-houses[k]);
            }
            if(distance[i]===undefined){
                distance[i]=[];
            }
            distance[i][j]=dist;
        }
    }
    return dp(0,k);
    function dp(i,k){
        let cacheKey=i+"_"+k;
        if(cache[cacheKey]!==undefined){
            return cache[cacheKey];
        }
        let min=Number.MAX_SAFE_INTEGER,ans;
        if(i===houses.length && k===0){//Its a correct answer only if we have used all the mailboxes and all the houses are completed. 
            return 0;
        }
        if(i===houses.length || k===0){//Other than the first if condition, every other condition to exhaust either mailboxes for houses is an invalid answer. So returning minus an infinite number from here. 
            return min;
        }
        
        for(let j=i;j<houses.length;j++){//Here in each step we are covering houses from ith index to jth index with one mailbox and calling dp function to cover the rest of the houses, starting from jth+1 index with the remaining k-1 houses. In each possible answer we will keep the minimum ans. 
            ans = dp(j+1,k-1)+distance[i][j];
            min = Math.min(min,ans);
        }
        cache[cacheKey]=min;
        return min;
    }
};
Allocate Mailboxes