Minimum Cost to Connect Two Groups of Points

This approach also uses top-down dynamic programming but optimizes the transition step. In the previous approach, for each point i in group 1, we iterated through all 2^size2 possible connection subsets, leading to a high time complexity. We can optimize this search for the best connection subset for point i.

1. Define a DP state dp[mask] as the minimum cost to connect the first i points of group 1 such that the points in group 2 represented by mask are covered.
2. We can use a 1D DP array dp of size 2^size2 and iterate from i = 1 to size1. The dp array at the beginning of iteration i will store the results for the first i-1 points.
3. For each point i from group 1, we need to update the dp table. Let dp_prev be the table for i-1 points and dp_curr be the table for i points.
4. The transition is dp_curr[mask] = min_{prev_mask | p_mask = mask, p_mask > 0} (dp_prev[prev_mask] + cost_for_p_mask). Here, cost_for_p_mask is the cost to connect point i-1 to the subset p_mask of group 2.
5. This transition is an OR-convolution in min-plus algebra. A naive implementation takes O(4^size2) time. We can optimize this using subset convolution techniques.
6. The transition can be rewritten as dp_curr[mask] = min_{sub ⊂ mask, sub>0} (dp_prev[mask \ sub] + cost_for_sub). This is a subset convolution.
7. Subset convolution can be computed efficiently using Sum over Subsets (SOS) DP. The overall complexity for computing one dp_curr table from dp_prev becomes O(size2^2 * 2^size2).
8. After iterating through all size1 points, the final answer is not yet dp[(1<<size2)-1]. The DP state only ensures that the first size1 points are connected. We still need to ensure all points in group 2 are connected.
9. A better approach is to use the Top-Down DP from the previous method but optimize the transition for connecting point i.
10. Instead of iterating through all 2^size2 subsets for point i, we can build the connection subset for i recursively. Define a helper function findMinForI(i, mask, j, p_mask) that finds the minimum cost by deciding whether to connect i to j or not, and recursing for j+1. This avoids the O(4^size2) complexity.
11. The state for this helper function can be memoized. For a fixed (i, mask) from the outer recursion, the helper's state is (j, p_mask), leading to an O(size2 * 2^size2) transition.

We can optimize the transition solve(i, mask) by creating a helper function that builds the optimal connection for point i more efficiently. Instead of a brute-force loop over 2^size2 subsets, this helper function, let's call it findMinForI, will decide for each point j in group 2 whether to include it in point i's connection set or not.

The helper function findMinForI(j, p_mask) would compute the minimum cost for connecting point i to a subset of points {j, ..., size2-1} given that i is already connected to p_mask from points {0, ..., j-1}. The state of this helper function is (j, p_mask), where j is the current point in group 2 being considered, and p_mask is the subset of connections for point i built so far.

findMinForI(j, p_mask):

• Base Case: When j == size2, we have considered all points in group 2 for connection to i. If p_mask is empty, it means i was not connected, which is invalid (return infinity). Otherwise, the total cost is solve(i + 1, mask | p_mask).
• Recursive Step: For point j, we have two choices:
  1. Don't connect i to j: The cost is findMinForI(j + 1, p_mask).
  2. Connect i to j: The cost is cost[i][j] + findMinForI(j + 1, p_mask | (1 << j)).
• The function returns the minimum of these two choices.

The main solve(i, mask) function will call findMinForI(0, 0) to find the best connection for point i. The helper function findMinForI can be memoized on its state (j, p_mask). Since this helper is called within solve(i, mask), its memoization table must be reset for each state (i, mask) of the outer recursion.

This optimization reduces the complexity of the transition. For each state (i, mask), we solve a subproblem of size O(size2 * 2^size2). The total complexity becomes O(size1 * size2 * 2^size2).

class Solution {
    private int size1, size2;
    private List<List<Integer>> cost;
    private int[] minCostG2;
    private Integer[][] memo;
    private Integer[][] memo_helper;

    public int minCostConnectTwoGroups(List<List<Integer>> cost) {
        this.cost = cost;
        this.size1 = cost.size();
        this.size2 = cost.get(0).size();
        this.minCostG2 = new int[size2];
        
        for (int j = 0; j < size2; j++) {
            int minC = Integer.MAX_VALUE;
            for (int i = 0; i < size1; i++) {
                minC = Math.min(minC, cost.get(i).get(j));
            }
            minCostG2[j] = minC;
        }
        
        this.memo = new Integer[size1][1 << size2];
        return solve(0, 0);
    }

    private int solve(int i, int mask) {
        if (i == size1) {
            int remainingCost = 0;
            for (int j = 0; j < size2; j++) {
                if ((mask & (1 << j)) == 0) {
                    remainingCost += minCostG2[j];
                }
            }
            return remainingCost;
        }

        if (memo[i][mask] != null) {
            return memo[i][mask];
        }

        // Memoization for the helper function, specific to the state (i, mask)
        // Although 'i' and 'mask' are not passed to findMinForI, they define the context
        // in which it's called. The recursive calls from findMinForI depend on them.
        memo_helper = new Integer[size2 + 1][1 << size2];
        int res = findMinForI(i, mask, 0, 0);
        return memo[i][mask] = res;
    }

    private int findMinForI(int i, int mask, int j, int p_mask) {
        if (j == size2) {
            if (p_mask == 0) {
                return 1_000_000_000; // Invalid path, point i not connected
            }
            return solve(i + 1, mask | p_mask);
        }

        if (memo_helper[j][p_mask] != null) {
            return memo_helper[j][p_mask];
        }

        // Option 1: Don't connect point i to point j
        int res = findMinForI(i, mask, j + 1, p_mask);

        // Option 2: Connect point i to point j
        res = Math.min(res, cost.get(i).get(j) + findMinForI(i, mask, j + 1, p_mask | (1 << j)));
        
        return memo_helper[j][p_mask] = res;
    }
}