Minimum Cost to Connect Two Groups of Points LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<int>> dp;
4

5
  int recurs(vector<vector<int>> &cost, vector<int> &v, int i, int mask) {
6
    if (dp[i][mask] != -1) return dp[i][mask];
7

8
    if (i < cost.size()) {
9
      int res = INT_MAX;
10
      for (int j = 0; j < cost[0].size(); j++)
11
        res = min(res, recurs(cost, v, i + 1, (mask | (1 << j))) + cost[i][j]);
12
      return dp[i][mask] = res;
13
    } else {
14
      int res = 0;
15
      for (int j = 0; j < cost[0].size(); j++) res += v[j] * (!(mask & (1 << j)));
16
      return dp[i][mask] = res;
17
    }
18
  }
19

20
  int connectTwoGroups(vector<vector<int>> &cost) {
21
    dp.resize(cost.size() + 1, vector<int>(5000, -1));
22

23
    vector<int> v(cost[0].size(), 0);
24

25
    for (int j = 0; j < cost[0].size(); j++) {
26
      int m = INT_MAX;
27
      for (int i = 0; i < cost.size(); i++) m = min(m, cost[i][j]);
28
      v[j] = m;
29
    }
30

31
    return recurs(cost, v, 0, 0);
32
  }
33
};