[leetcode] 1478. Allocate Mailboxes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1478. Allocate Mailboxes
Source            : leetcode.com
Category          : Dynamic Programin
Algorithm         : 3D DP 
Verdict           : Accepted

1. class Solution {  
2. public:  
3.     const int INF = 1e9;  
4.     int dp[101][101][101];  
5.       
6.     int minDistance(vector<int>& houses, int k) {  
7.         int n = houses.size();  
8.         sort(houses.begin(), houses.end());  
9.         memset(dp, -1, sizeof dp);  
10.           
11.         function <int(int, int)> get = [&](int l, int r) {  
12.             int sum = 0;  
13.             int median = (l + r) / 2;  
14.             median = houses[median];  
15.             for (int i = l; i <= r; i++) {  
16.                 sum += abs(houses[i] - median);  
17.             }  
18.             return sum;  
19.         };  
20.           
21.         function <int(int, int, int)> solve = [&](int now, int pre, int block) {  
22.             if (block > k) {  
23.                 return INF;  
24.             }   
25.             if (now == n - 1) {  
26.                 if (block < k) {  
27.                     return INF;  
28.                 }  
29.                 return get(pre, now);  
30.             }    
31.             if (now == n) {  
32.                 return INF;  
33.             }  
34.             int &ret = dp[now][pre][block];  
35.             if (~ret) {  
36.                 return ret;  
37.             }  
38.             ret = solve(now + 1, pre, block);  
39.             int go = get(pre, now) + solve(now + 1, now + 1, block + 1);  
40.             ret = min(ret, go);  
41.             return ret;  
42.         };  
43.         int ans = solve(0, 0, 1);  
44.         return ans;  
45.     }  
46. };