Assume there are 4 points in first group, labeled with **0**, **1**, **2**, **3**. 3 points in second group, labeled with **A**, **B**, **C**.

Define dp[i][j]. Use binary to symbolize **j**,** **for example dp[2][6] = dp[2][(110)]. This means minimum cost for first 3 (0, 1, 2) points in first group connecting with **B**, **C** points in second group. In another way, write it like dp[2][CB*]

dp[3][C*A] = min{

dp[3][**A] + cost[3][C], // make a new connection in same row

dp[3][C**] + cost[3][A],

dp[2][**A] + cost[3][C], // no C in row 2, C is new in row 3. build connection 3->C

dp[2][C**] + cost[3][A],

dp[2][C*A] + cost[3][C], // CA is already included in row2, reuse C in row 3.

dp[2][C*A] + cost[3][A]

}

Code:

public static int connectTwoGroups(List<List<Integer>> cost) {
int col = cost.get(0).size();
int[][] memo = new int[cost.size()][1 << col];
for (int[] m : memo) {
Arrays.fill(m, Integer.MAX_VALUE);
}
dfs(cost.size() - 1, (1 << col) - 1, memo, cost);
return dfs(cost.size() - 1, (1 << col) - 1, memo, cost);
}
private static int dfs(int row, int b, int[][] memo, List<List<Integer>> cost) {
if (memo[row][b] != Integer.MAX_VALUE) {
return memo[row][b];
}
if ((b - (b & (-b))) == 0) { // b only has 1 one in binary
int col = 0;
while ((b & (1 << col)) == 0) {
col++;
}
memo[row][b] = 0;
for (int i = 0; i <= row; i++) {
memo[row][b] += cost.get(i).get(col);
}
return memo[row][b];
}
if (row == 0) {
memo[row][b] = 0;
for (int i = 0; i < cost.get(0).size(); i++) {
if ((b & (1 << i)) > 0) {
memo[row][b] += cost.get(0).get(i);
}
}
return memo[row][b];
}
for (int col = 0; col < cost.get(0).size(); col++) {
if ((b & (1 << col)) > 0) {
memo[row][b] = Math.min(memo[row][b], dfs(row, b - (1 << col), memo, cost) + cost.get(row).get(col));
memo[row][b] = Math.min(memo[row][b], dfs(row - 1, b - (1 << col), memo, cost) + cost.get(row).get(col));
memo[row][b] = Math.min(memo[row][b], dfs(row - 1, b, memo, cost) + cost.get(row).get(col));
}
}
return memo[row][b];
}