<p>You are given two groups of points where the first group has <code>size<sub>1</sub></code> points, the second group has <code>size<sub>2</sub></code> points, and <code>size<sub>1</sub> &gt;= size<sub>2</sub></code>.</p>

<p>The <code>cost</code> of the connection between any two points are given in an <code>size<sub>1</sub> x size<sub>2</sub></code> matrix where <code>cost[i][j]</code> is the cost of connecting point <code>i</code> of the first group and point <code>j</code> of the second group. The groups are connected if <strong>each point in both groups is connected to one or more points in the opposite group</strong>. 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.</p>

<p>Return <em>the minimum cost it takes to connect the two groups</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex1.jpg" style="width: 322px; height: 243px;" />
<pre>
<strong>Input:</strong> cost = [[15, 96], [36, 2]]
<strong>Output:</strong> 17
<strong>Explanation</strong>: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex2.jpg" style="width: 322px; height: 403px;" />
<pre>
<strong>Input:</strong> cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
<strong>Output:</strong> 4
<strong>Explanation</strong>: 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>size<sub>1</sub> == cost.length</code></li>
	<li><code>size<sub>2</sub> == cost[i].length</code></li>
	<li><code>1 &lt;= size<sub>1</sub>, size<sub>2</sub> &lt;= 12</code></li>
	<li><code>size<sub>1</sub> &gt;= size<sub>2</sub></code></li>
	<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>
</ul>

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
class Solution{

    public:
// Global DP table
int dp[13][4096] = {};

// Depth-First Search (DFS) function to calculate the minimum cost
int dfs(vector<vector<int>>& cost, vector<int>& min_cost_for_each_col, int row, int mask) {
    // If the result for this state has already been calculated, return it
    if (dp[row][mask]) {
        return dp[row][mask] - 1;  // Subtract 1 because we added 1 during storage
    }
    
    int res;
    int num_rows = cost.size();
    int num_cols = cost[0].size();
    
    if (row >= num_rows) {
        // Base case: All rows have been processed
        res = 0;
        // Add the minimum cost for any columns that haven't been covered yet
        for (int col = 0; col < num_cols; ++col) {
            if (!(mask & (1 << col))) { // If the column `col` is not yet covered
                res += min_cost_for_each_col[col];
            }
        }
    } else {
        // Recursive case: Consider all columns for the current row
        res = INT_MAX;
        for (int col = 0; col < num_cols; ++col) {
            // Choose the minimum cost between all possible column selections
            res = min(res, cost[row][col] + dfs(cost, min_cost_for_each_col, row + 1, mask | (1 << col)));
        }
    }
    
    // Store the result in the DP table and return it
    dp[row][mask] = res + 1; // Add 1 to avoid zero ambiguity in the dp table
    return res;
}

int connectTwoGroups(vector<vector<int>>& cost) {
    int num_rows = cost.size();
    int num_cols = cost[0].size();

    // Precompute the minimum cost to connect each column with any row
    vector<int> min_cost_for_each_col(num_cols, INT_MAX);
    for (int col = 0; col < num_cols; ++col) {
        for (int row = 0; row < num_rows; ++row) {
            min_cost_for_each_col[col] = min(min_cost_for_each_col[col], cost[row][col]);
        }
    }

    // Start the DFS from the first row with no columns covered initially (mask = 0)
    return dfs(cost, min_cost_for_each_col, 0, 0);
}


};
10300