Allocate Mailboxes LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} houses
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var minDistance = function (houses, k) {
7
  let n = houses.length;
8
  let sorted = houses.sort((a, b) => a - b);
9
  costs = new Array(n);
10
  for (let i = 0; i < n; i++) {
11
    costs[i] = new Array(n).fill(0);
12
  }
13
  const memo = new Array(100);
14

15
  for (let i = 0; i < 100; i++) {
16
    memo[i] = new Array(100);
17
  }
18

19
  for (let i = 0; i < n; i++) {
20
    for (let j = 0; j < n; j++) {
21
      let median = sorted[Math.floor((i + j) / 2)];
22
      for (let t = i; t < j + 1; t++) {
23
        costs[i][j] += Math.abs(median - sorted[t]);
24
      }
25
    }
26
  }
27

28
  const dp = (k, i) => {
29
    if (k === 0 && i === n) return 0;
30
    if (k === 0 || i === n) return Infinity;
31
    if (memo[k][i] != null) return memo[k][i];
32
    let ans = Infinity;
33
    for (let j = i; j < n; j++) {
34
      let cost = costs[i][j];
35
      ans = Math.min(ans, cost + dp(k - 1, j + 1));
36
    }
37
    memo[k][i] = ans;
38
    return ans;
39
  };
40

41
  return dp(k, 0);
42
};