# 1478. Allocate Mailboxes

• Time: $O(n^3 + kn^2) = O(n^3)$;
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: int minDistance(vector& houses, int k) { const int n = houses.size(); // dp[i][j] := min distance to allocate i mailboxes in houses[j:] dp.resize(k + 1, vector(n, INT_MAX)); // cost[i][j] := minCost to allocate mailbox between houses[i] and houses[j] cost.resize(n, vector(n)); sort(begin(houses), end(houses)); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { const int median = houses[(i + j) / 2]; for (int x = i; x <= j; ++x) cost[i][j] += abs(houses[x] - median); } return minDistance(houses, k, 0); } private: constexpr static int kMax = 1'000'000; vector> dp; vector> cost; int minDistance(const vector& houses, int k, int i) { if (k == 0 && i == houses.size()) return 0; if (k == 0 || i == houses.size()) return kMax; if (dp[k][i] != INT_MAX) return dp[k][i]; for (int j = i; j < houses.size(); ++j) dp[k][i] = min(dp[k][i], cost[i][j] + minDistance(houses, k - 1, j + 1)); return dp[k][i]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public int minDistance(int[] houses, int k) { final int n = houses.length; // dp[i][j] := min distance to allocate i mailboxes in houses[j:] dp = new int[k + 1][n]; Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE)); // cost[i][j] := minCost to allocate mailbox between houses[i] and houses[j] cost = new int[n][n]; Arrays.sort(houses); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { final int median = houses[(i + j) / 2]; for (int x = i; x <= j; ++x) cost[i][j] += Math.abs(houses[x] - median); } return minDistance(houses, k, 0); } private static final int kMax = 1_000_000; private int[][] dp; private int[][] cost; private int minDistance(int[] houses, int k, int i) { if (k == 0 && i == houses.length) return 0; if (k == 0 || i == houses.length) return kMax; if (dp[k][i] != Integer.MAX_VALUE) return dp[k][i]; for (int j = i; j < houses.length; ++j) dp[k][i] = Math.min(dp[k][i], cost[i][j] + minDistance(houses, k - 1, j + 1)); return dp[k][i]; } }