The trick here is to name the state correctly, then let the implementation follow. For 1478. Allocate Mailboxes, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming.
The notes already sitting in the source point us in the right direction:
- recursion
- TLE
- 31 / 69 test cases passed.
- https://leetcode.com/problems/allocate-mailboxes/discuss/685620/JavaC%2B%2BPython-Top-down-DP-Prove-median-mailbox-O(n3)
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, minDistance.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//recursion
02//TLE
03//31 / 69 test cases passed.
04//https://leetcode.com/problems/allocate-mailboxes/discuss/685620/JavaC%2B%2BPython-Top-down-DP-Prove-median-mailbox-O(n3)
05class Solution {
06public:
07 /*
08 1 <= houses.length <= 100
09 1 <= houses[i] <= 10^4
10 1 <= k <= houses.length
11
12 one mailbox's cost: at most 100*1e4
13 k mailboxes' cost: at most 100*100*1e4
14 */
15 int MAX = 1e8;
16
17 int dfs(vector<int>& houses, int k, int start){
18 if(k == 0 && start == houses.size()) return 0;
19 if(k == 0 || start == houses.size()) return MAX;
20
21 int ans = MAX;
22
23 for(int end = start; end < houses.size(); end++){
24 /*
25 put one mailbox in [start, end] and
26 remaining k-1 mailboxes in [end+1, n-1]
27 */
28 /*
29 if there are even houses,
30 cost is minimum when mailbox is put inbetween
31 the two middle houses
32 if there are odd houses,
33 cost is minimum when mailbox is put at the middle house
34 */
35 int median = houses[(start+end)/2];
36 int cost = 0;
37 for(int i = start; i <= end; i++){
38 cost += abs(houses[i] - median);
39 }
40 ans = min(ans, cost + dfs(houses, k-1, end+1));
41 }
42
43 return ans;
44 };
45
46 int minDistance(vector<int>& houses, int k) {
47 //this is important because we need to calculate median!
48 sort(houses.begin(), houses.end());
49 return dfs(houses, k, 0);
50 }
51};
52
53//recursion + memorization
54//https://leetcode.com/problems/allocate-mailboxes/discuss/685620/JavaC%2B%2BPython-Top-down-DP-Prove-median-mailbox-O(n3)
55//Runtime: 748 ms, faster than 16.67% of C++ online submissions for Allocate Mailboxes.
56//Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Allocate Mailboxes.
57class Solution {
58public:
59 int MAX = 1e8;
60 vector<vector<int>> memo;
61
62 int dfs(vector<int>& houses, int k, int start){
63 if(k == 0 && start == houses.size()) return 0;
64 if(k == 0 || start == houses.size()) return MAX;
65 if(memo[k][start] != 0) return memo[k][start];
66
67 int ans = MAX;
68
69 for(int end = start; end < houses.size(); end++){
70 int median = houses[(start+end)/2];
71 int cost = 0;
72 for(int i = start; i <= end; i++){
73 cost += abs(houses[i] - median);
74 }
75 ans = min(ans, cost + dfs(houses, k-1, end+1));
76 }
77
78 return memo[k][start] = ans;
79 };
80
81 int minDistance(vector<int>& houses, int k) {
82 sort(houses.begin(), houses.end());
83 //k = 0 for padding
84 memo = vector<vector<int>>(k+1, vector<int>(houses.size()));
85 return dfs(houses, k, 0);
86 }
87};
88
89//recursion + memorization + cache cost
90//https://leetcode.com/problems/allocate-mailboxes/discuss/685620/JavaC%2B%2BPython-Top-down-DP-Prove-median-mailbox-O(n3)
91//Runtime: 284 ms, faster than 66.67% of C++ online submissions for Allocate Mailboxes.
92//Memory Usage: 9.2 MB, less than 66.67% of C++ online submissions for Allocate Mailboxes.
93//time: O(n^3 + k*n^2), O(n^3) for calculating cost, O(k*n^2) for k*n states of dp, each takes O(n)
94//space: O(n^2)
95class Solution {
96public:
97 int MAX = 1e8;
98 vector<vector<int>> cost;
99 vector<vector<int>> memo;
100
101 int dfs(vector<int>& houses, int k, int start){
102 if(k == 0 && start == houses.size()) return 0;
103 if(k == 0 || start == houses.size()) return MAX;
104 if(memo[k][start] != 0) return memo[k][start];
105
106 int ans = MAX;
107
108 for(int end = start; end < houses.size(); end++){
109 ans = min(ans, cost[start][end] + dfs(houses, k-1, end+1));
110 }
111
112 return memo[k][start] = ans;
113 };
114
115 int minDistance(vector<int>& houses, int k) {
116 int n = houses.size();
117 sort(houses.begin(), houses.end());
118 memo = vector<vector<int>>(k+1, vector<int>(n));
119
120 //precalculate cost of [i, j]
121 cost = vector<vector<int>>(n, vector<int>(n));
122 for(int i = 0; i < n; i++){
123 for(int j = i; j < n; j++){
124 for(int k = i; k <= j; k++){
125 cost[i][j] += abs(houses[(i+j)/2] - houses[k]);
126 }
127 }
128 }
129
130 return dfs(houses, k, 0);
131 }
132};
133
134//bottom-up dp
135//Runtime: 36 ms, faster than 100.00% of C++ online submissions for Allocate Mailboxes.
136//Memory Usage: 9.4 MB, less than 50.00% of C++ online submissions for Allocate Mailboxes.
137class Solution {
138public:
139 int MAX = 1e8;
140
141 int minDistance(vector<int>& houses, int k) {
142 int n = houses.size();
143 sort(houses.begin(), houses.end());
144
145 vector<vector<int>> dp(k+1, vector<int>(n+1));
146
147 vector<vector<int>> cost(n, vector<int>(n));
148 for(int i = 0; i < n; i++){
149 for(int j = i; j < n; j++){
150 for(int k = i; k <= j; k++){
151 cost[i][j] += abs(houses[(i+j)/2] - houses[k]);
152 }
153 }
154 }
155
156 //if(k == 0 && start == houses.size()) return 0;
157 dp[0][n] = 0;
158 //if(k == 0 || start == houses.size()) return MAX;
159 for(int start = 1; start < n; start++){
160 dp[0][start] = MAX;
161 }
162 for(int kk = 1; kk <= k; kk++){
163 dp[kk][n] = MAX;
164 }
165
166 for(int kk = 1; kk <= k; kk++){
167 for(int start = 0; start < n; start++){
168 int res = MAX;
169 for(int end = start; end < n; end++){
170 res = min(res, cost[start][end] + dp[kk-1][end+1]);
171 }
172
173 dp[kk][start] = res;
174 }
175 }
176
177 return dp[k][0];
178 }
179};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.