1595. 连通两组点的最小成本

给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.Arrays;
import java.util.List;

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        if (cost == null || cost.size() == 0 || cost.get(0).size() == 0) {
            return 0;
        }
        int m = cost.size(), n = 1 << cost.get(0).size();
        int[][] dp = new int[m + 1][n];
        int inf = Integer.MAX_VALUE / 2;
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], inf);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int k = 1; k < n; k++) {
                for (int j = 0; j < cost.get(0).size(); j++) {
                    if (((k >> j) & 1) != 0) {
                        dp[i][k] = Math.min(dp[i][k], dp[i - 1][k ^ (1 << j)] + cost.get(i - 1).get(j));
                        dp[i][k] = Math.min(dp[i][k], dp[i][k ^ (1 << j)] + cost.get(i - 1).get(j));
                        dp[i][k] = Math.min(dp[i][k], dp[i - 1][k] + cost.get(i - 1).get(j));
                    }
                }
            }
        }
        return dp[m][n - 1];
    }
}