You are given two groups of points where the first group has size1
points, the second group has size2
points, and size1 >= size2
.
The cost
of the connection between any two points are given in an size1 x size2
matrix where cost[i][j]
is the cost of connecting point i
of the first group and point j
of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.
Return the minimum cost it takes to connect the two groups.
Example 1:
Input: cost = [[15, 96], [36, 2]] Output: 17 Explanation: The optimal way of connecting the groups is: 1--A 2--B This results in a total cost of 17.
Example 2:
Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]] Output: 4 Explanation: The optimal way of connecting the groups is: 1--A 2--B 2--C 3--A This results in a total cost of 4. Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
Example 3:
Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]] Output: 10
Constraints:
size1 == cost.length
size2 == cost[i].length
1 <= size1, size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100
Solution 1: Bistmask DP
dp[i][s] := min cost to connect first i (1-based) points in group1 and a set of points (represented by a bitmask s) in group2.
ans = dp[m][1 << n – 1]
dp[i][s | (1 << j)] := min(dp[i][s] + cost[i][j], dp[i-1][s] + cost[i][j])
Time complexity: O(m*n*2^n)
Space complexity: O(m*2^n)
C++/Bottom up
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int connectTwoGroups(vector<vector<int>>& cost) { constexpr int kInf = 1e9; const int m = cost.size(); const int n = cost[0].size(); // dp[i][s] := min cost to connect first i points in group1 // and points (bitmask s) in group2. vector<vector<int>> dp(m + 1, vector<int>(1 << n, kInf)); dp[0][0] = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) for (int s = 0; s < 1 << n; ++s) dp[i + 1][s | (1 << j)] = min({dp[i + 1][s | (1 << j)], dp[i + 1][s] + cost[i][j], dp[i][s] + cost[i][j]}); return dp[m].back(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment