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

Description Link to heading

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

Solution Link to heading

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 Link to heading

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];
    }
};