LeetCode 1595: Minimum Cost to Connect Two Groups of Points

Explanation

To solve this problem, we can use dynamic programming with bitmasking. We will iterate over all possible subsets of points from the first group and find the minimum cost of connecting these points to the points in the second group. We will keep track of the minimum cost for each subset of points in the first group.

1. Create a dp array of size 2^size1 to store the minimum cost for each subset of points in the first group.
2. Initialize dp array with maximum cost except for the empty subset (cost 0).
3. Iterate over all possible subsets of points in the first group.
4. For each subset, iterate over all points in the second group and find the minimum cost of connecting these points to the subset.
5. Update the dp array with the minimum cost for each subset.
6. Finally, return the minimum cost of connecting the two groups.

Time Complexity: O(2^size1 * size2) Space Complexity: O(2^size1)

class Solution {
    public int connectTwoGroups(int[][] cost) {
        int size1 = cost.length;
        int size2 = cost[0].length;
        
        int[][] dp = new int[1 << size1][size2];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        
        for (int mask = 0; mask < (1 << size1); mask++) {
            for (int j = 0; j < size2; j++) {
                for (int i = 0; i < size1; i++) {
                    dp[mask | (1 << i)][j] = Math.min(dp[mask | (1 << i)][j], dp[mask][j] + cost[i][j]);
                    dp[mask][j] = Math.min(dp[mask][j], dp[mask][j] + cost[i][j]);
                }
            }
        }
        
        return dp[(1 << size1) - 1][size2 - 1];
    }
}