最大兼容性评分和

难度: Medium

有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。

这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。

每个学生都会被分配给一名导师，而每位导师也会分配到一名学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。

例如，学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。

请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。

给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。

示例 1：

输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
输出：8
解释：按下述方式分配学生和导师：
- 学生 0 分配给导师 2 ，兼容性评分为 3 。
- 学生 1 分配给导师 0 ，兼容性评分为 2 。
- 学生 2 分配给导师 1 ，兼容性评分为 3 。
最大兼容性评分和为 3 + 2 + 3 = 8 。

示例 2：

输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
输出：0
解释：任意学生与导师配对的兼容性评分都是 0 。

提示：

m == students.length == mentors.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k] 为 0 或 1
mentors[j][k] 为 0 或 1

Submission

运行时间: 51 ms

内存: 16.0 MB

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m, n = len(students), len(students[0])

        f = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(m):
                for k in range(n):
                    f[i][j] += int(students[i][k] == mentors[j][k])
            
        dp = [0] * (1 << m)
        dp[0] = 0
        for i in range(1, 1 << m):
            k = i.bit_count()
            for j in range(m):
                if i & (1 << j):
                    dp[i] = max(dp[i], dp[i ^ (1 << j)] + f[k - 1][j])
        
        return dp[-1]

Explain

此题解采用的是动态规划加状态压缩的策略。首先，计算学生与每位导师之间的兼容性评分，存储在二维数组 f 中，其中 f[i][j] 表示第 i 个学生与第 j 个导师的评分。接着，利用一个一维数组 dp 来存储状态压缩的动态规划结果，dp[i] 表示在状态 i 下的最大兼容性评分和。状态 i 是一个二进制数，表示当前已分配的导师集合。通过遍历所有的状态，并对于每个状态，在考虑分配下一个导师时更新 dp 数组，最终 dp 的最后一个元素即为最大兼容性评分和。

时间复杂度: O(m^2 n + m * 2^m)

空间复杂度: O(m^2 + 2^m)

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m, n = len(students), len(students[0])  # 获取学生和问题的数量

        f = [[0] * m for _ in range(m)]  # 初始化兼容性评分数组
        for i in range(m):
            for j in range(m):
                for k in range(n):
                    f[i][j] += int(students[i][k] == mentors[j][k])  # 计算每对学生和导师的兼容性评分

        dp = [0] * (1 << m)  # 初始化状态压缩的动态规划数组
        dp[0] = 0  # 空状态的最大兼容性评分和为 0
        for i in range(1, 1 << m):
            k = i.bit_count()  # 计算当前状态下的已分配导师数量
            for j in range(m):
                if i & (1 << j):
                    dp[i] = max(dp[i], dp[i ^ (1 << j)] + f[k - 1][j])  # 更新 dp 数组，尝试将第 j 个导师分配给第 k-1 个学生

        return dp[-1]  # 返回最大兼容性评分和

Explore

状态压缩是一种利用整数的二进制表示来表示集合的技术。在本问题中，每一位的0或1表示一个导师是否已经被分配。例如，如果有三位导师，二进制数 '101' 表示第一位和第三位导师已经被分配。状态压缩能够将问题的空间复杂度从指数级减少到多项式级别，因为它将可能的分配情况从列举每种情况简化为0到2^m-1的整数遍历。这种方法显著提高了算法的空间和时间效率，特别是在处理与组合相关的问题时非常有效。

在动态规划数组 `dp` 中，`dp[i]` 表示在状态i下的最大兼容性评分和。状态i是一个二进制数，每一位代表一个导师是否被分配。计算 `dp[i]` 的值是通过遍历所有可能的前一个状态来完成的。具体来说，对于每个状态i，我们检查每一位（每位代表一个导师），如果这位是1（即这位导师已分配），我们则尝试理解这位导师是如何被分配的。我们通过关闭这一位（将其从1变为0，使用位运算 i ^ (1 << j)）来获得一个新的状态，这个新状态代表一个没有当前导师的旧状态。然后，我们将这个旧状态的最大评分和加上当前导师和对应学生的兼容性评分（通过二维数组f计算），取所有可能的组合中的最大值，从而得到 `dp[i]`。

在动态规划中使用位运算来表示状态主要是因为它提供了一种高效的方式来处理和表示所有可能的组合状态。这种表示方式的优势在于：1) 它能够高效地使用内存和处理时间，因为状态转换（例如添加或删除一个元素）可以通过简单的位运算实现，这些操作通常比其他数据结构操作更快；2) 它天然适合处理二进制决策问题，如配对、选择等。然而，这种方法也有限制，主要是它仅适用于元素数量较少的情况（通常不超过20-30），因为状态的数量会随着集合大小呈指数增长，导致计算和存储成本急剧上升。