1595. Minimum Cost to Connect Two Groups of Points

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int m = cost.size(), n = cost.get(0).size();

        // 定义 dp[i][mask] 为从前 i 个数字中使用部分数字与掩码 mask 所对应的集合连接的最小成本
        int[][] dp = new int[m + 1][1 << n];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }
        dp[0][0] = 0;

        for (int i = 1; i <= m; i++) {
            for (int mask = 1; mask < dp[i].length; mask++) {
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) == 0) {
                        // i - 1 无法连接点 j, 跳过
                        continue;
                    }

                    // 使用 i - 1 连接 j 的成本 cost.get(i - 1).get(j)
                    dp[i][mask] = Math.min(dp[i][mask], dp[i - 1][mask] + cost.get(i - 1).get(j)); // 使用 i - 1 去连接 j, 且 i - 1 不再连接其他点
                    dp[i][mask] = Math.min(dp[i][mask], dp[i][mask ^ (1 << j)] + cost.get(i - 1).get(j)); // 使用 i - 1 去连接 j, 且 j 不再连接其他点
                    dp[i][mask] = Math.min(dp[i][mask], dp[i - 1][mask ^ (1 << j)] + cost.get(i - 1).get(j)); // 使用 i - 1 去连接 j, 且 i - 1 与 j 均不再连接其他点
                }
            }
        }

        return dp[m][(1 << n) - 1];
    }
}

References

1595. Minimum Cost to Connect Two Groups of Points