LeetCode 1947. 最大兼容性评分和（状态枚举DP）

1. 题目

有一份由 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-compatibility-score-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• dp[state] 老师被选择的情况是 state 的二进制位1 表示的状态时 的最大得分和

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        n = len(students)
        dp = [0 for _ in range(1<<n)]
        def score(x, y):
            return sum([1 if (xi^yi)==0 else 0 for xi, yi in zip(x, y)])
        # 预处理出来学生和老师的得分
        scores = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(n):
                scores[i][j] = score(students[i], mentors[j])

		# DP
        for i in range(0, n): # 枚举学生样本
            for state in range(0, 1<<n): # 枚举老师的状态
                if bin(state).count('1') == i: # 老师被选的个数应该为 i 个了
                    for j in range(n):
                        if state&(1<<j) == 0: # j 号 老师还没有被选
                            dp[state|(1<<j)] = max(dp[state] + scores[i][j], dp[state|(1<<j)])
        return dp[-1]

56 ms 14.9 MB Python3

上面是 state 是之前的状态

如果 state 是现在的状态，则代码是

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        n = len(students)
        dp = [0 for _ in range(1<<n)]
        def score(x, y):
            return sum([1 if (xi^yi)==0 else 0 for xi, yi in zip(x, y)])
        # 预处理出来学生和老师的得分
        scores = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(n):
                scores[i][j] = score(students[i], mentors[j])

		# DP
        for state in range(1, 1<<n): # 枚举老师的状态
            i = bin(state).count('1')  # 老师被选的个数 i 个, 当前学生下标是 i-1
            for j in range(n):
                if state&(1<<j): # 学生 i-1 选择了 j 号 老师
                    dp[state] = max(dp[state^(1<<j)] + scores[i-1][j], dp[state])
        return dp[-1]

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！