JZTXT

1595. Minimum Cost to Connect Two Groups of Points] (Hard)

发布时间 2023-06-21 12:37:34作者: zwyyy456

Description

1595. Minimum Cost to Connect Two Groups of Points (Hard)

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

Dynamic Programming + State Compression

We use a binary number $j$ to represent the set of chosen elements from the second group. $dp[i][j]$ denotes the minimum cost of connecting the first $i$ elements from the first group and the set of elements $j$ from the second group.

To establish the recurrence relation, we consider the elements from the first group. Let's focus on the $i$-th element and iterate through the elements $k$ in the set (where $k$ represents the element index). We encounter the following scenarios:

  • The $i$-th element is only connected to $k$. In this case, we have two possibilities:
    • The element in the second group with index $k$ is solely connected to the $i$-th element: $dp[i][j] = \min(dp[i][j], dp[i - 1][j\oplus(1 << k)] + \text{cost}[i - 1][k])$.
    • The element in the second group with index $k$ is connected to other elements as well: $dp[i][j] = \min(dp[i][j], dp[i - 1][j] + \text{cost}[i - 1][k])$.
  • The $i$-th element is connected to elements other than $k$. In this case, we also have two possibilities:
    • The element in the second group with index $k$ is solely connected to the $i$-th element: $dp[i][j] = \min(dp[i][j], dp[i][j\oplus (1 << k)] + \text{cost}[i - 1][k])$.
    • The element in the second group with index $k$ is connected to other elements besides the $i$-th element. At this point, the $i$-th element does not need to be connected to the element with index $k$ anymore. Thus, we can eliminate the unnecessary edge. If we forcibly connect the $i$-th element and element $k$, redundant edges will be introduced. Therefore, we consider the aforementioned three cases by enumerating $k_1$, $k$, or $k_2$.

Please note that each time we iterate through $k$, we need to compare it with the previously calculated $dp[i][j]$! Additionally, if the condition in the for loop is not satisfied, the loop will terminate.

Code

class Solution {
  public:
    int connectTwoGroups(vector<vector<int>> &cost) {
        int m = cost.size(), n = cost[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(1 << n, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j < (1 << n); ++j) {
                for (int k = 0; (1 << k) <= j; ++k) {
                    if (((1 << k) & j) == 0) {
                        continue;
                    }
                    int tmp = min(dp[i][j ^ (1 << k)], min(dp[i - 1][j ^ (1 << k)], dp[i - 1][j])) + cost[i - 1][k];
                    dp[i][j] = min(tmp, dp[i][j]);
                }
            }
        }
        return dp[m][(1 << n) - 1];
    }
};