Allocate Mailboxes LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[101][101];
4
  int solve(vector<int> &houses, int pos, int k) {
5
    if (k < 0) return 1e9;
6
    if (pos >= houses.size()) return k ? 1e9 : 0;
7
    if (dp[pos][k] != -1) return dp[pos][k];
8

9
    // at current position pos, spread the group from (pos upto j) and allot
10
    // this whole group 1 mailbox. start new neigbour at j + 1
11

12
    int ans = INT_MAX;
13
    for (int j = pos; j < houses.size(); ++j) {
14
      int middle = (pos + j) / 2, cost = 0;
15
      // cost calculation
16
      for (int i = pos; i <= j; ++i) cost += abs(houses[middle] - houses[i]);
17

18
      ans = min(ans, cost + solve(houses, j + 1, k - 1));
19
    }
20
    return dp[pos][k] = ans;
21
  }
22
  int minDistance(vector<int> &houses, int k) {
23
    sort(begin(houses), end(houses));
24
    memset(dp, -1, sizeof(dp));
25

26
    return solve(houses, 0, k);
27
  }
28
};