每日一题：连通两组点的最小成本

题意

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

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

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

Solution

$dp[i][j]$ 表示左部前 $i$ 个点连接右部(1<<m)的情况，状态转移方程：dp[i][now | 1 << j] = min({dpnow | 1 << j, dp[i - 1][j] + cost[i - 1]j + 当前点连接右边第j个点}, dp[i][j] + cost[i - 1]j + 当前点连接右边第j个点))。

Code

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int n = cost.size();
        int m = cost.get(0).size();
        int all = 1 << m;
        int[][] dp = new int[n + 1][all];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], 2000000000);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int now = 0; now < all; now++) {
                for (int j = 0; j < m; j++) {
                    dp[i][now | 1 << j] = Math.min(dp[i][now | 1 << j], Math.min(dp[i - 1][now] + cost.get(i - 1).get(j), dp[i][now] + cost.get(i - 1).get(j)));
                }
            }
        }
        return dp[n][all - 1];
    }
}